ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 2"
| แถว 21: | แถว 21: | ||
return -1 | return -1 | ||
else | else | ||
| − | + | k=(b+e)/2 | |
| − | if a[ | + | if a[k] = k |
| − | return | + | return k |
| − | else if a[ | + | else if a[k] > k |
| − | retrun FindI(a, | + | retrun FindI(a,b,k-1) |
| − | else if a[ | + | else if a[k] < k |
| − | return FindI(a,k+1, | + | return FindI(a,k+1,e) |
} | } | ||
</geshi> | </geshi> | ||
ซึ่งเวลาการทำงานของอัลกอริทึมดังกล่าวก็จะเป็น <math> O(\log n) \,</math> เหมือน binary serach พอดี | ซึ่งเวลาการทำงานของอัลกอริทึมดังกล่าวก็จะเป็น <math> O(\log n) \,</math> เหมือน binary serach พอดี | ||
รุ่นแก้ไขปัจจุบันเมื่อ 04:22, 28 กรกฎาคม 2553
อินพุต: อะเรย์ ที่เรียงจากน้อยไปหามากแล้ว โดยที่ตัวเลขทุกตัวในอะเรย์มีค่าต่างกัน
เอาพุต: ตอบว่ามี ถ้ามี และไม่มีถ้ากรณีดังกล่าวไม่เป็นจริง
วัตถุที่เราต้องตรวจสอบคือ ตัวเลข โดยที่เงื่อนไขคือ ตัวเลข ที่อยู่ในช่วงดังกล่าวที่ทำให้ และโจทย์ต้องการให้เวลาการทำงานทั้งหมดเป็น ดังนั้นเราจะใช้ 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 พอดี
