418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 1

อินพุต: อะเรย์ $A[.]\,$ ที่มีขนาดเป็น infinity ที่มีคุณสมบัติคือสมาชิกชิก $n\,$ ตัวแรกมีค่าเป็นศูนย์ นอกนั้นมีค่าเป็นหนึ่ง

เอาพุต: ค่า $n\,$

วัตถุ ที่เราต้องทำการตรวจสอบในข้อนี้คือ ตัวเลข 1,2,3,... (หรือ index ของอะเรย์นั่นเอง) ซึ่ง ค่า $n\,$ จะเป็นค่าที่อยู่ในช่วงดังกล่าว และมีเงื่อนไขคือ A[0]ถึง A[n]มีค่าเป็นศูนย์ และ A[n+1] เป็นต้นไปมีค่าเป็นหนึ่ง (เขียนสั้น ๆ คือ A[n]=0 และ A[n+1]=1) แต่โจทย์ต้องการให้เวลาในการหาค่า $n\,$ ดังกล่าวเป็น $O(\log n)\,$ จากการตัวอย่างการค้นหาในห้องเรียน เราได้เรียน binary search ไปแล้ว เราจะใช้วิธีดังกล่าว

วิธีการค้นหาจะทำดังนี้ ให้เริ่มค้นหาก่อนว่าค่าของอะเรย์ในตำแหน่งต่อไปนี้เป็นศูนย์หรือไม่ ตำแหน่งดังกล่าวคือ $2^{1},2^{2},2^{3},...,2^{j}$ จากในห้องเรียนเราได้เห็นแล้วว่าเงื่อนไขของ binary search มีสามเงื่อนไขคือ หยุด ไปทางซ้าย และไปทางขวา สำหรับข้อนี้เงื่อนไขเหล่านี้จะเป็นดังนี้

เงื่อนไขหยุด คือ A[k]=0 and A[k+1]=1

เงื่อนไขไปทางซ้ายคือ A[k]=1 and A[k+1]=1 // แสดงว่าวิ่งเกินมาทางขวาเกินไปแล้ว คำตอบต้องอยู่ทางซ้ายแน่นอน

เงื่อนไขไปทางขวาคือ A[k]=0 and A[k+1]=0 // แสดงว่าวิ่งยังไม่ถึงคำตอบ วิ่งช้าไป คำตอบต้องอยู่ทางขวาแน่นอน

เมื่อนำแนวคิดดังกล่าวมาเขียนเป็น pseudocode จะได้ดังนี้

FindN(a,i,j)

if j<i

return -1

else

for i=1 to j

k=2^i

if a[k]=0 and a[k+1]=1

return k

else if a[k]=1 and a[k+1]=1

return FindN(a,i,k-1)

else

return FindN(a,k+1,j)

เวลาการทำงานของอัลกอริทึมคือ จะทำทั้งหมด $2^{j}\,$ รอบ โดยที่เรารู้ว่า $n\leq 2^{j}<2n\,$ ดังนั้นเวลาการทำงานคือ $O(2^{j})=O(\log n)\,$ นั่นเอง