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

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

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

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

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

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

เงื่อนไขหยุดคือ $A[i]=i\,$

เงื่อนไขไปทางซ้ายคือ $A[i]>i\,$

เงื่อนไขไปทางขวาคือ $A[i]<i\,$

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

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)

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