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

การค้นหาแบบทวิภาคอย่างมีเอกรูป (Uniform binary search) เป็นการค้นหาแบบทวิภาค (binary search) ชนิดหนึ่งซึ่งลดขนาดการทำงานของการค้นหาแบบปกติลง ขั้นตอนวิธีนี้ได้ถูกคิดค้นขึ้นโดย โดนัลด์ คนูธ และได้เขียนแนวคิดและการพิสูจน์ประสิทธิภาพไว้ในหนังสือ The Art of Computer Programming,Volume 3
ลักษณะการทำงานโดยรวมของการค้นหาแบบทวิภาคอย่างมีเอกรูป จะคล้ายๆกับการค้นหาแบบทวิภาคแบบธรรมดา แต่จะต่างกันที่การเลือกจุดพิจารณาว่าจะคิดจากตัวแปร และการที่การค้นหาแบบทวิภาคอย่างมีเอกรูป ได้ทำการคำนวณค่า
ที่จะพิจารณาไว้ก่อนค้นหานั้น จะทำให้ความเร็วในการทำงานเพิ่มขึ้นโดยเฉลี่ยประมาณ 17% เทียบกับการค้นหาแบบทวิภาคแบบธรรมดา แต่ประสิทธิภาพเชิงเวลาที่คำนวณได้จะมีค่าเท่ากันกับ
ประสิทธิภาพเชิงเวลาของการค้นหาแบบทวิภาพแบบธรรมดา นั่นคือ O(log n) ดังนั้นขั้นตอนวิธีแบบการค้นหาแบบทวิภาคอย่างมีเอกรูป จึงไม่ค่อยได้ถูกนำไปใช้กันมากนัก ทั้งนี้อาจเกิดจากการเขียนโค้ดที่ยุ้งยากกว่า
แต่ได้ประสิทธิภาพเชิงเวลาเท่ากับการค้นหาแบบทวิภาพแบบธรรมดา
== แนวคิด ==
การค้นหาแบบทวิภาคอย่างมีเอกรูป จะมีแนวคิดคล้ายๆกับการค้นหาแบบทวิภาค แต่จะต่างกันตรงที่ วิธีค้นหาในการค้นหาแบบทวิภาคจะเสมือนการหักครึ่งการพิจารณาไปเรื่อยๆ จนสามารถสรุปได้ว่าเจอตัวที่ค้นหาหรือไม่ ส่วนการค้นหาแบบทวิภาคอย่างมีเอกรูปจะไม่ได้ทำการหักครึ่งค้นหา แต่ลำดับการค้นหาจะเป็นไปตามค่าที่เราคำนวณไว้ตั้งแต่ก่อนค้นหาแล้ว
== แนวทางการเขียน Uniform Binary Search ==
สำหรับขั้นตอนวิธีในการทำงานของ Uniform Binary Search เริ่มต้นจากการสร้าง อาเรย์สำรวจ ขึ้นมาไว้เก็บดัชนีที่จะใช้กระโดดไปพิจารณาในอาเรย์ข้อมูลของเรา โดยตั้งค่าเริ่มต้นให้เป็น 0 ทั้งหมด จากนั้นเราจะสร้างฟังก์ชันขึ้นมา ซึ่งฟังก์ชันนี้จะมีหน้าที่ในการเติมค่าดัชนีลงในอาเรย์สำรวจ เพื่อเป็นการบอกระยะของตำแหน่งที่จะพิจารณาถัดไปเมื่อเทียบกับตำแหน่งปัจจุบัน โดยจะมีวิธีการเติมค่าของอาเรย์สำรวจ ตามตัวอย่างโค้ดภาษา C ด้านล่าง
void make_delta(int n){
int power = 1;
int i = 0;
do{
int half = power;
power 
อธิบายการทำงานของฟังก์ชันได้ดังนี้ power เป็นตัวแปรไว้เก็บค่า 2^n โดยกำหนดตัวแปร n ให้เริ่มที 0 ส่วนตัวแปร i เป็น ดันชีชี้ตำแหน่งของ อาเรย์สำรวจและภายในวงวนจะทำการเติมค่าใน อาเรย์สำรวจ ไปเรื่อยๆ จนกว่าจะเติมด้วยเลข 0 จึงหยุดวงวน (ซึ่งแสดงว่าระยะกระโดดเพื่อไปยังตำแหน่งอื่นเป็น 0 ก็หมายถึงไม่ต้องกระโดแล้ว) ส่วนวิธีเติมเลขลงไปใน อาเรย์สำรวจ นั้นได้มาจากทางสูตรคณิตศาสตร์ที่อยู่ในหนังสือ the art of computer programming หน้า 415 สูตรที่ 6 \text{DELTA}[j]=\left\lfloor\frac{N+2^{j-1} }{2^j}\right\rfloor,\qquad\text{for }1\le j\le \lfloor\lg N\rfloor+2 ซึ่งได้มาจากการพิสูจน์และสรุปผลทางคณิตศาสตร์ เพื่อประกันว่าการกระโดดแบบนี้จะพิจารณาข้อมูลภายในอาเรย์ข้อมูลของเราได้อย่างครบถ้วนแล้ว
ส่วนต่อมาจะเป็นส่วนฟังก์ชัน ของการค้นหาข้อมูลในอาเรย์ ข้อมูลของเราโดยลักษณะการทำงานทั่วๆไปจะเหมือนกันการค้นหาแบบทวิภาคแบบธรรมดา แต่จะเปลี่ยนจากการคำนวณค่าของการกระโดด จากตัวแปรที่ชื่อ left,right ที่รับเข้ามา เป็นการอ้างอิงระยะการกระโดดจากอาเรย์สำรวจ ซึ่งมีผลทำให้ใช้เวลาเร็วกว่า Binary Search ซึ่งตัวอย่างโค้ดภาษา C การทำงานของฟังก์ชันนี้ มีดังนี้
int unisearch(int *a, int key){
int i = delta[0] - 1; // จะเริ่มค้นหาที่ตำแหน่งกึ่งกลางของ อาเรย์ข้อมูล เสมอ
int d = 0;
while(1){
if(key == a[i]) return i;
else if(delta[d] == 0) return -1;
if(key 
อธิบายการทำงานของฟังก์ชัน ใน 2 กรณีแรก คือการเจอข้อมูลที่ค้นหาจะคืนค่า ตำแหน่งที่พบ ส่วนถ้าไม่เจอข้อมูลใดเลย (ภายในอาเรย์สำรวจ จะเก็บค่า 0 คือ ไม่ต้องกระโดดต่อแล้ว) ก็จะคืน -1 ส่วนกรณีอื่นๆก็จะทำงานเหมือนกับ Binary Search ปกติ กล่าวคือ จะเทียบค่าที่ต้องการค้นหากับ ค่าของอาเรย์ข้อมูลว่ามากกว่าหรือน้อยกว่าข้อมูลในช่องที่กำลังพิจารณาอยู่ ก็ให้เลื่อนตำแหน่งพิจารณาไปพิจารณาช่างที่หาไปทางซ้ายหรือทางขวา ซึ่งมีระยะห่างจากตำแหน่งปัจจุบันเท่ากับค่าที่เก็บในอาเรย์สำรวจ
สามารถอธิบายการทำงานของโปรแกรมด้วย Flow Chart ดังนี้

== อ้างอิง ==
โดนัลด์ คนูธ. The Art of Computer Programming, Volume 3. Page 412, Algorithm C.
ขั้นตอนวิธีการค้นหา