การค้นหาแบบทวิภาคอย่างมีเอกรูป

การค้นหาแบบทวิภาคอย่างมีเอกรูป (อังกฤษ: Uniform binary search) เป็นการค้นหาแบบทวิภาค (binary search) ชนิดหนึ่งซึ่งลดขนาดการทำงานของการค้นหาแบบปกติลง ขั้นตอนวิธีนี้ได้ถูกคิดค้นขึ้นโดย โดนัลด์ คนูธ และได้เขียนแนวคิดและการพิสูจน์ประสิทธิภาพไว้ในหนังสือ The Art of Computer Programming,Volume 3

ลักษณะการทำงานโดยรวมของการค้นหาแบบทวิภาคอย่างมีเอกรูป จะคล้ายๆกับการค้นหาแบบทวิภาคแบบธรรมดา แต่จะต่างกันที่การเลือกจุดพิจารณาว่าจะคิดจากตัวแปร การค้นหาแบบทวิภาคอย่างมีเอกรูป ได้ทำการคำนวณค่า ที่จะพิจารณาไว้ก่อนค้นหานั้น จะทำให้ความเร็วทำงานเพิ่มขึ้นโดยเฉลี่ยประมาณ 17% เทียบกับการค้นหาแบบทวิภาคแบบธรรมดา แต่ประสิทธิภาพเชิงเวลาที่คำนวณได้จะมีค่าเท่ากันกับ ประสิทธิภาพเชิงเวลาของการค้นหาแบบทวิภาพแบบธรรมดา นั่นคือ O(log n) ดังนั้นขั้นตอนวิธีแบบการค้นหาแบบทวิภาคอย่างมีเอกรูป จึงไม่ค่อยได้ถูกนำไปใช้กันมากนัก ทั้งนี้อาจเกิดจากการเขียนโค้ดที่ยุ้งยากกว่า แต่ได้ประสิทธิภาพเชิงเวลาเท่ากับการค้นหาแบบทวิภาพแบบธรรมดา

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

สำหรับขั้นตอนวิธีทำงานของ Uniform Binary Search เริ่มต้นจากการสร้าง อาเรย์สำรวจ ขึ้นมาไว้เก็บดัชนีที่จะใช้กระโดดไปพิจารณาในอาเรย์ข้อมูลของเรา โดยตั้งค่าเริ่มต้นให้เป็น 0 ทั้งหมด จากนั้นเราจะสร้างฟังก์ชันขึ้นมา ซึ่งฟังก์ชันนี้จะมีหน้าที่ในการเติมค่าดัชนีลงในอาเรย์สำรวจ เพื่อเป็นการบอกระยะของตำแหน่งที่จะพิจารณาถัดไปเมื่อเทียบกับตำแหน่งปัจจุบัน โดยจะมีวิธีการเติมค่าของอาเรย์สำรวจ ตามตัวอย่างโค้ดภาษา C ด้านล่าง

อธิบายการทำงานของฟังก์ชันได้ดังนี้ power เป็นตัวแปรไว้เก็บค่า 2^n โดยกำหนดตัวแปร n ให้เริ่มที 0 ส่วนตัวแปร i เป็น ดันชีชี้ตำแหน่งของ อาเรย์สำรวจและภายในวงวนจะทำการเติมค่าใน อาเรย์สำรวจ ไปเรื่อยๆ จนกว่าจะเติมด้วยเลข 0 จึงหยุดวงวน (ซึ่งแสดงว่าระยะกระโดดเพื่อไปยังตำแหน่งอื่นเป็น 0 ก็หมายถึงไม่ต้องกระโดแล้ว) ส่วนวิธีเติมเลขลงไปใน อาเรย์สำรวจ นั้นได้มาจากทางสูตรคณิตศาสตร์ที่อยู่ในหนังสือ the art of computer programming หน้า 415 สูตรที่ 6 DELTA[j]=?N+2j?12j?,for 1?j??lg?N?+2{\displaystyle {\text{DELTA}}[j]=\left\lfloor {\frac {N+2^{j-1}}{2^{j}}}\right\rfloor ,\qquad {\text{for }}1\leq j\leq \lfloor \lg N\rfloor +2} ซึ่งได้มาจากการพิสูจน์และสรุปผลทางคณิตศาสตร์ เพื่อประกันว่าการกระโดดแบบนี้จะพิจารณาข้อมูลภายในอาเรย์ข้อมูลของเราได้อย่างครบถ้วนแล้ว

ส่วนต่อมาจะเป็นส่วนฟังก์ชัน ของการค้นหาข้อมูลในอาเรย์ ข้อมูลของเราโดยลักษณะการทำงานทั่วๆไปจะเหมือนกันการค้นหาแบบทวิภาคแบบธรรมดา แต่จะเปลี่ยนจากการคำนวณค่าของการกระโดด จากตัวแปรที่ชื่อ left,right ที่รับเข้ามา เป็นการอ้างอิงระยะการกระโดดจากอาเรย์สำรวจ ซึ่งมีผลทำให้ใช้เวลาเร็วกว่า Binary Search ซึ่งตัวอย่างโค้ดภาษา C การทำงานของฟังก์ชันนี้ มีดังนี้

อธิบายการทำงานของฟังก์ชัน ใน 2 กรณีแรก คือการเจอข้อมูลที่ค้นหาจะคืนค่า ตำแหน่งที่พบ ส่วนถ้าไม่เจอข้อมูลใดเลย (ภายในอาเรย์สำรวจ จะเก็บค่า 0 คือ ไม่ต้องกระโดดต่อแล้ว) ก็จะคืน -1 ส่วนกรณีอื่นๆก็จะทำงานเหมือนกับ Binary Search ปกติ กล่าวคือ จะเทียบค่าที่ต้องการค้นหากับ ค่าของอาเรย์ข้อมูลว่ามากกว่าหรือน้อยกว่าข้อมูลในช่องที่กำลังพิจารณาอยู่ ก็ให้เลื่อนตำแหน่งพิจารณาไปพิจารณาช่างที่หาไปทางซ้ายหรือทางขวา ซึ่งมีระยะห่างจากตำแหน่งปัจจุบันเท่ากับค่าที่เก็บในอาเรย์สำรวจ