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

อินพุต: อะเรย์ <math> A[.] \, </math> ที่เรียงจากน้อยไปหามากแล้ว โดยที่ตัวเลขทุกตัวในอะเรย์มีค่าต่างกัน

เอาพุต: ตอบว่ามี ถ้ามี <math>A[i]=i \,</math> และไม่มีถ้ากรณีดังกล่าวไม่เป็นจริง

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

เนื่องจากเราใช้ binary search เราต้องรู้ให้ได้ว่าเงื่อนไขสามเงื่อนไขที่ใช้ในการตรวจสอบคืออะไร

แน่นอนว่าเงื่อนไขในการหยุดคือ <math>A[i]=i \,</math> พิจารณากรณีที่ <math>A[i]< i \,</math> สมมติให้ <math>A[i]=x \,</math> เนื่องจากอะเรย์เรียงจากน้อยไปมากแล้ว ดังนั้นเมื่อพิจารณาอะเรย์ฝั่งซ้ายของตำแหน่งที่ <math> i \, </math> จะได้ <math>A[i-1]\leq x-1,A[i-2]\leq x-2,A[i-3]\leq x-3 \, </math> สำหรับ index <math>i-1, i-2, i-3, ...</math> ดังนั้นคำตอบ <math> i \, </math> ที่จะทำให้ <math>A[i]=i \,</math> จึงไม่อยู่ในฝั่งซ้ายนี้แน่นอน เพราะว่าค่าในอะเรย์ทุกค่าน้อยกว่า ค่า index มันหมดเลย ดังนั้นเราจึงควรไปค้นหาในฝั่งขวา และเมื่อพิจารณาแบบเดียวกันก็จะได้เงื่อนไขทั้งสามเงื่อนไขเป็นดังนี้

:เงื่อนไขหยุดคือ <math>A[i]=i \,</math>
:เงื่อนไขไปทางซ้ายคือ <math>A[i]>i \,</math>
:เงื่อนไขไปทางขวาคือ <math>A[i]<i \,</math>

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

<geshi lang="c">
FindI(a,b,e)
{
if e < b
    return -1
else
    i=(b+e)/2
    if a[i] = i
        return i
    else if a[i] > i
        retrun FindI(a,i,k-1)
    else if a[i] < i
        return FindI(a,k+1,j)
}
</geshi>

ซึ่งเวลาการทำงานของอัลกอริทึมดังกล่าวก็จะเป็น <math> O(\log n) \,</math> เหมือน binary serach พอดี