การค้นหาแบบทวิภาค

การใช้ในงานทั่วไป

การค้นหาในข้อมูลที่มีการเรียงลำดับแล้วในงานทั่วไป เช่น พจนานุกรมที่มีการเรียงรายการของคำและความหมาย ถ้ารู้คำเราก็จะสามารถหาความหมายได้, สมุดโทรศัพท์ที่มีการเรียงลำดับรายการชื่อ, ที่อยู่ และเบอร์โทรศัพท์ หากรู้ชื่อก็จะหาเบอร์โทรศัพท์และที่อยู่ได้อย่างรวดเร็ว
ถ้ารายการที่ได้ค้นหามีข้อมูลเล็กน้อยเช่น 1โหล การค้นหาแบบทวิภาคจะใช่เวลาเพียงเล็กน้อยเมื่อเปรียบเทียบกับการค้นหาแบบเชิงเส้น แต่มันต้องการรายการที่มีการเรียงลำดับมาแล้ว คล้ายกับตารางแฮชหรือการค้นหาแบบแฮชที่มีความเร็วมากกว่าการค้นหาแบบทวิภาคแต่ยังมีลักษณะของข้อมูลที่ค่อนข้างเจาะจงกว่าด้วยเช่นกัน ถ้ารู้ว่าต้องทำการค้นหาเป็นจำนวนหลายครั้งหรือลักษณะของข้อมูลตรงกับที่ต้องการแล้วควรเลือกใช้การค้นหาแบบทวิภาค แต่ถ้าต้องค้นหาเพียงไม่ก็ครั้งหรือเพียงครั้งเดียวการเลือกใช้การค้นหาแบบเชิงเส้นก็น่าจะเป็นตัวเลือกที่ดีที่สุด

เกมเดาตัวเลข

นี่คือเกมพื้นฐานที่ใช้หลักการเดียวกันกับขั้นตอนวิธีนี้โดยเริ่มจากคำพูดว่า "ผมกำหนดจำนวนเต็มหนึ่งจำนวนที่มีค่าระหว่าง 40 ถึง 60 และเพื่อที่คุณจะเดาได้ ผมจะบอกว่า 'มากกว่า', 'น้อยกว่า' หรือ 'ใช่!' เมื่อคำตอบถูกต้อง" การค้นหาข้อมูลจำนวน "N" ข้อมูลที่เป็นไปได้ดังนั้นมากกว่า  คำถามที่ต้องถาม หรือกล่าวง่ายๆว่าเกมจะต้องกำหนดจำนวนคำถามมากกว่า  คำถาม เมื่อมีการถามแต่ละครั้งพื้นที่ในการค้นหาแต่ละครั้งก็จะถูกแบ่งครึ่งไปเรื่อยๆ ดังนั้นจำนวนการค้นหาจึงถูกบีบให้อยู่ในช่วงๆหนึ่ง แม้ว่าจำนวนที่จะเดามีขนาดใหญ่ก็ตาม, ในกรณีที่ไม่มีขอบเขตบนก็จะสามารถค้นหาได้ที่ประสิทธิภาพ  เริ่มด้วยหาขอบเขตบนโดยการเพิ่มค่าที่เดาซ้ำแล้วซ้ำอีก ตัวอย่างเช่น คำตอบคือ 11 โดยจะเดาเป็นแบบรูปดังนี้ 1(มากกว่า), 2(มากกว่า), 4(มากกว่า), 8(มากกว่า), 16(น้อยกว่า), 12(น้อยกว่า), 10(มากกว่า) และนี่เรารู้ว่าจำนวนนั้นคือ 11 เพราะเป็นจำนวนที่มากกว่า 10 และน้อยกว่า 12 ถ้าลองใช้วิธีการนี้กับจำนวนเต็มลบและศูนย์บ้าง เช่น จะหา −13: 0, −1, −2, −4, −8, −16, −12, −14 ในที่สุดแล้วก็จะรู้ว่าเลขที่ต้องการคือ -13 เพราะเป็นเลขที่น้อยกว่า -12 และมากกว่า -14

รายการของคำ

ในการค้นหาทั่วไปมีการใช้การค้นหาแบบทวิภาคและการค้นหาแบบสอดแทรกโดยที่ไม่รู้ตัว เมื่อจะหารายชื่อของบุคคลในสมุดโทรศัพท์ เราต้องเริ่มด้วยการเดาจนเมื่อเรารู้ว่ารายการที่กำลังค้นหานั้นได้มีการเรียงลำดับแล้ว นั่นทำให้เราสามารถค้นหารายชื่อที่ต้องการได้อย่างรวดเร็ว เช่น ถ้าจะหาชื่อ "สมชาย" แต่ถ้าเราเปิดไปเจอหน้าที่มีชื่อ "ศรราม" เราก็จะพลิกไปหน้าถัดๆไปที่เราคะเนไว้ว่าจะมีชื่อที่ต้องการ หากหน้าที่พริกไปนั่นมีชื่อ "องอาจ" ดังนั้นจะสรุปได้ว่ารายชื่อของ "สมชาย" ก็จะอยู่ระหว่างหน้าของ "ศรราม" กับ "องอาจ" ซึ่งขั้นตอนดังกล่าวจะทำให้เราแบ่งปัญหาให้เป็นปัญหาย่อยได้

แบบเวียนเกิด

การค้นหาแบบทวิภาคสามารถใช้การเรียกซ้ำได้ โดยมีสิ่งที่ต้องการคือพารามิเตอร์อันได้แก่ แถวลำดับที่มีการเรียงลำดับมากแล้ว(ในต้วอย่างจะเป็นการเรียงลำดับจากน้อยไปมาก) และแน่นอนว่าต้องสามารถอ้างถึงแถวลำดับตรงการด้วยดัชนี(index)ต้นและปลายของแถวลำดับ ซึ่งพารามิเตอร์เหล่านี้จะทำให้สามารถเรียกฟังก์ชันแบบเรียกซ้ำได้ และโดยขั้นตอนวิธีแล้ว การเขียนการค้นหาแบบทวิภาคด้วยการเวียนเกิดหรือเรียกซ้ำนั้นคอมไพเลอร์จะไม่มีการสร้างกองซ้อนกองใหม่ขึ้นมาโดยจะใช้เพียงกองเดียวเท่านั้น พิจารณาที่ตัวแปร a คือแถวลำดับที่ต้องการค้นหา key คือค่าของตัวแปรที่ต้องการค้นหาในแถวลำดับ a left คือดัชนีของต้นแถวลำดับ a และ right คือดัชนีของปลายแถวลำดับ a
int binary_search(int a[], int key, int left, int right){
    if(left > right)    //ถ้าค่าของ left มากกว่า right แสดงว่าแถวลำดับย่อยไม่มีสมาชิกเหลืออยู่แล้ว และไม่มี key ที่ต้องการ
        return -1;  //คืนค่าที่ต้องการแสดงว่าไม่พบค่า key
    else    //ถ้ายังมีสมาชิกอยู่ก็ทำการค้นหาต่อไป
    {
        int mid = (left+right)/2;   //mid ดัชนีตรงกลางของแถวลำดับย่อยหรือหลัก
        if(a[mid]>key)  //ถ้าค่าตรงกลางของแถวลำมีค่ามากกว่า key แสดงว่า key ต้องอยู่ระหว่าง a[left] กับ a[mid-1]
            return binary_search(a,key,left,mid-1); //ดังนั้นจึงไปค้นหาต่อในแถวลำดับย่อยระหว่าง left และ mid-1
        if(a[mid]<key)  //ในทำนองเดียวกันกับ  ค่าตรงกลางของแถวลำมีค่ามากกว่า key
            return binary_search(a,key,mid+1,right);
        if(a[mid]==key) //หากค่าตรงการของแถวลำกับมีค่าเท่ากับ key แสดงว่าพบแล้ว
            return mid; //คืนค่าตำแหน่งของ key ในแถวลำดับ a กลับไป
    }}
โดยจะให้ค่าของ left เท่ากับ 0 และ right เท่ากับ N-1 สำหรับแถวลำดับที่มีจุดเริ่มที่ศูนย์และมีสมาชิก N ตัว ดังนั้นเราจึงได้ค่าของ mid หรือ ดัชนีที่ชี้ตรงกลางของแถวลำดับที่เริ่มต้นที่ left ถึง right นั่นคือจะมีค่าเท่ากับ (left+right)/2

การวนซ้ำ

การค้นหาแบบทวิภาคยังสามารถในแบบการวนซ้ำได้เนี่องจากการค้นหาแบบนี้มีการทำงานเป็นเชิงเส้นไม่ได้มีการแตกการทำงานแต่อย่างใด
 1 int binary_search(int a[], int key, int left, int right) 2 { 3     while (left <= right) 4     { 5         int mid = (left+right)/2; 6         if (a[mid] < key) 7             left = mid + 1; 8         else if (a[mid] > key) 9             right = mid - 1;10         else //พบ key ในแถวลำดับ a แล้ว11             return mid;12     }13     // ไม่พบ key14     return -1;15 }

ประสิทธิภาพ

ในแต่ละการทดสอบที่ล้มเหลวในการค้นหาจำนวนที่มีค่าตรงกันจะเป็นกรณีที่มีจำนวนการทำงานมากที่สุด โดยถ้า "N" เป็นจำนวนคี่จะแบ่งช่วงย่อยเป็น ("N"-1)/2 และถ้าเป็นจำนวนคู่จะแบ่งเป็นช่วงละ "N"/2-1 และ "N"/2
ถ้าจำนวนแถวลำดับตอนเริ่มต้นเท่ากับ "N" จะถูกแบ่งเป็นประมาณ "N"/2 แล้วแบ่งเป็น "N"/4 แล้วเป็น "N"/8 ไปเรื่อยๆ โดยในกรณีที่แย่ที่สุดเกิดเมื่อค่าที่ต้องการไม่อยู่ในแถวลำดับ จะทำการคำนวณ ⌊log₂(N)+1⌋ ครั้ง เมื่อเราเปรียบเทียบกับการค้นหาเชิงเส้น พฤติกรรมการทำงานของกรณีแย่ที่สุดของแต่ะมันจะเป็น "N" เราจะเห็นได้ว่าการค้นหาแบบทวิภาคจะเร็วกว่าในกรณีที่ความยาวของแถวลำดับเป็น "N" ยกตัวอย่างเช่น ถ้าจะค้นหาในรายการที่มีจำนวนสมาชิกล้านตัวมันจะทำการวนซ้ำประมาณล้านรอบสำหรับการค้นหาแบบเชิงเส้น แต่มันจะไม่มากกว่า 20 ครั้งสำหรับการค้นหาแบบทวิภาค แต่อย่างไรก็ตามการค้นหาแบบทวิภาคก็ต้องค้นหาได้ในเพียงแถวลำดับที่มีการเรียงลำดับแล้ว