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

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

เอาพุต: ค่า <math> n \, </math>

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

วิธีการค้นหาจะทำดังนี้ ให้เริ่มค้นหาก่อนว่าค่าของอะเรย์ในตำแหน่งต่อไปนี้  <math>2^1, 2^2,2^3,...,2^j \,</math> เป็นศูนย์หรือไม่ การค้นหาดังกล่าวทำเพื่อที่จะจำกัดช่วงของคำตอบว่าค่าที่ต้องการอยู่ในช่วงไหนกันแน่ เพราะจากโจทย์ขนาดของอะเรย์ที่เป็นอินพุตมีขนาดไม่จำกัด ดังนั้นการหาค่ากลางจะทำไม่ได้ พอได้ช่วงของคำตอบที่เป็นไปได้ที่เป็นช่วงจำกัดมา เราจึงทำการหาแบบ 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 จะหยุดทำเมื่อค่า <math> n \leq 2^j < 2n \,</math> ซึ่งจะทำงานทั้งหมด <math> j \, </math> รอบ ส่วน FindN จะทำการหาค่า <math> n\, </math> ในช่วงย่อยที่อยู่ระหว่างค่าศูนย์กับหนึ่งแล้ว ซึ่งทำงานทั้งหมด <math> O(\log 2^j)=O(\log n) \,</math> รอบ ดังนั้นเวลาการทำงานทั้งหมดจะเป็น <math> j+O(\log n)=O(\log n) </math> รอบ