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

การค้นหาแบบทวิภาคอย่างมีเอกรูป (อังกฤษ: 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 <<= 1;
        delta[i] = (n + half) / power; // delta[] คือ อาเรย์สำรวจ
    }while(delta[i++] != 0);
}

อธิบายการทำงานของฟังก์ชันได้ดังนี้ 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\leq j\leq \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 < a[i]) i -= delta[++d];
        else i += delta[++d];
    }
}

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

สามารถอธิบายการทำงานของโปรแกรมด้วย Flow Chart ดังนี้

อ้างอิง

• โดนัลด์ คนูธ. The Art of Computer Programming, Volume 3. Page 412, Algorithm C.