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 อีกทีว่าค่าที่ต้องการอยู่ตรงไหน

จากในห้องเรียนเราได้เห็นแล้วว่าเงื่อนไขของ 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 จะได้ดังนี้ (รอบแรกของการทำงานให้ ให้ j=1)

FindInterval(a,j)

if j<0

return -1

else

k = 2^j

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

return k

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

return FindN(a,2^(j-1),2^j)

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

return FindInterval(a,j+1)

FindN(a,i,j)

if j<i

return -1

else

k = (i+j)/2

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

return k

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

return FindN(a,k+1,j)

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

return FindN(a,i,k-1)

เวลาการทำงานของอัลกอริทึมจะแบ่งออกเป็นการค้นหาใน FindN และการค้นหาใน FindInterval ซึ่ง FindInterval จะหยุดทำเมื่อค่า $n\leq 2^{j}<2n\,$ ซึ่งจะทำงานทั้งหมด $j\,$ รอบ ส่วน FindN จะทำการหาค่า $n\,$ ในช่วงย่อยที่อยู่ระหว่างค่าศูนย์กับหนึ่งแล้ว ซึ่งทำงานทั้งหมด $O(\log 2^{j})=O(\log n)\,$ รอบ ดังนั้นเวลาการทำงานทั้งหมดจะเป็น $j+O(\log n)=O(\log n)$ รอบ