พูดคุย:การค้นหาแบบทวิภาค

เนื้อหาเพิ่มเติมที่ไม่มีในบทความภาษาอังกฤษ (จากคุณ Pantarut)

ขั้นตอนวิธี

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

การค้นหาแบบทวิภาคสามารถใช้การเรียกซ้ำได้ โดยมีสิ่งที่ต้องการคือพารามิเตอร์อันได้แก่ แถวลำดับที่มีการเรียงลำดับมาแล้ว (ในต้วอย่างจะเป็นการเรียงลำดับจากน้อยไปมาก) ซึ่งสามารถอ้างถึงแถวลำดับตรงกลางได้ด้วยดัชนี (index) ต้น และปลายของแถวลำดับ ซึ่งพารามิเตอร์เหล่านี้จะทำให้สามารถเรียกฟังก์ชันแบบเรียกซ้ำได้ และโดยขั้นตอนวิธีแล้ว การเขียนการค้นหาแบบทวิภาคด้วยการเวียนเกิดหรือเรียกซ้ำนั้น คอมไพเลอร์จะไม่มีการสร้างกองซ้อนกองใหม่ขึ้นมา โดยจะใช้เพียงกองเดียวเท่านั้น พิจารณาตัวแปร $A$ คือแถวลำดับที่ต้องการค้นหา, $T$ คือค่าของตัวแปรที่ต้องการค้นหาในแถวลำดับ $A$, $L$ คือดัชนีของต้นแถวลำดับ $A$, $R$ คือดัชนีของปลายแถวลำดับ $A$ และ $n$ คือจำนวนแถวลำดับของข้อมูล

function binary_search(A, T, L, R) is
    if L > R then
        return unsuccessful
    else:
        m := floor((L + R) / 2)
        if A[m] < T then
            return binary_search(A, T, m + 1, R)
        else if A[m] > T then
            return binary_search(A, T, L, m - 1)
        else:
            return m Amxxch (คุย) 20:01, 9 สิงหาคม 2565 (+07)

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

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

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

ตัวอย่าง

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

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

รายการของคำ

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