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)

<geshi lang="c"> 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) // วิ่งไปหาช่วงต่อไปในอะเรย์ด้านขวา

</geshi>

<geshi lang="c"> 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,i,k-1)
   else if a[k]= 0 and a[k+1]=0
       return FindN(a,k+1,j)

</geshi>

เวลาการทำงานของอัลกอริทึมจะแบ่งออกเป็นการค้นหาใน 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)$ รอบ