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

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

เอาพุต: ตอบว่ามี ถ้ามี และไม่มีถ้ากรณีดังกล่าวไม่เป็นจริง

วัตถุที่เราต้องตรวจสอบคือ ตัวเลข โดยที่เงื่อนไขคือ ตัวเลข ที่อยู่ในช่วงดังกล่าวที่ทำให้ และโจทย์ต้องการให้เวลาการทำงานทั้งหมดเป็น ดังนั้นเราจะใช้ binary search ที่เรียนกันไปในห้องเรียน

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

แน่นอนว่าเงื่อนไขในการหยุดคือ พิจารณากรณีที่ สมมติให้ เนื่องจากอะเรย์เรียงจากน้อยไปมากแล้ว ดังนั้นเมื่อพิจารณาอะเรย์ฝั่งซ้ายของตำแหน่งที่ จะได้ สำหรับ index ดังนั้นคำตอบ ที่จะทำให้ จึงไม่อยู่ในฝั่งซ้ายนี้แน่นอน เพราะว่าค่าในอะเรย์ทุกค่าน้อยกว่า ค่า index มันหมดเลย ดังนั้นเราจึงควรไปค้นหาในฝั่งขวา และเมื่อพิจารณาแบบเดียวกันก็จะได้เงื่อนไขทั้งสามเงื่อนไขเป็นดังนี้

เงื่อนไขหยุดคือ

เงื่อนไขไปทางซ้ายคือ

เงื่อนไขไปทางขวาคือ

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

<geshi lang="c"> FindI(a,b,e) { if e < b

   return -1

else

   k=(b+e)/2
   if a[k] = k
       return k
   else if a[k] > k
       retrun FindI(a,b,k-1)
   else if a[k] < k
       return FindI(a,k+1,e)

} </geshi>

ซึ่งเวลาการทำงานของอัลกอริทึมดังกล่าวก็จะเป็น เหมือน binary serach พอดี