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

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

บทความนี้อ้างอิงคริสต์ศักราช/คริสต์ทศวรรษ/คริสต์ศตวรรษ ซึ่งเป็นสาระสำคัญของเนื้อหา

ในสาขาวิทยาการคอมพิวเตอร์ การค้นหาแบบทวิภาค (อังกฤษ: binary search, half-interval search,^[1] logarithmic search,^[2] หรือ binary chop^[3]) เป็นขั้นตอนวิธีเพื่อหาตำแหน่งของค่าเป้าหมายในแถวลำดับที่ได้มีการเรียงลำดับข้อมูลแล้ว^[4]^[5] ขั้นตอนวิธีจะการเปรียบเทียบค่าเป้าหมายกับค่าของสมาชิกที่อยู่ตรงกลางของแถวลำดับ ถ้าทั้งสองมีค่าเท่ากันแสดงว่าพบค่าเป้าหมายที่ต้องการ ซึ่งจะทำการคืนค่าตำแหน่งหรือในที่นี้คือ ดัชนี (index) กลับไป มิฉะนั้นถ้าค่าเป้าหมายมีค่าน้อยกว่าค่าของสมาชิกตรงกลางของแถวลำดับ ก็จะทำขั้นตอนวิธีนี้อีกครั้งแต่เปลี่ยนมาค้นหาในแถวลำดับย่อยครึ่งหนึ่งที่มีจุดสิ้นสุดที่ตรงกลางของแถวลำดับหลัก หรือถ้าค่าเป้าหมายมีค่ามากกว่าแล้วจะค้นหาในแถวลำดับย่อยเช่นกันแต่ย้ายจุดเริ่มต้นมาที่ตรงกลางของแถวลำดับหลัก และดำเนินการค้นหาวนซ้ำไปเรื่อย ๆ จนกว่าจะพบค่าเป้าหมาย เมื่อการค้นหาดำเนินการจนแถวลำดับย่อยไม่มีสมาชิกอยู่ แสดงว่าไม่มีสมาชิกในแถวลำดับตัวใดที่มีค่าเท่ากับค่าเป้าหมาย และคืนค่าว่าไม่พบค่าเป้าหมาย

ในกรณีแย่ที่สุด การค้นหาแบบทวิภาคจะดำเนินงานโดยมีความซับซ้อนของเวลาในรูปลอการิทึม ซึ่งจะมีค่า $O(\log n)$ เมื่อ $n$ คือจำนวนแถวลำดับของข้อมูล^[a]^[6] การค้นหาแบบทวิภาคจะใช้เวลาดำเนินงานน้อยกว่าการค้นหาแบบเชิงเส้น [en] ยกเว้นในกรณีที่แถวลำดับมีจำนวนน้อย อย่างไรก็ตาม แถวลำดับนั้นจะต้องมีการเรียงลำดับข้อมูลก่อนจึงจะสามารถดำเนินการค้นหาแบบทวิภาคได้ นอกจากการค้นหาแบบทวิภาคแล้ว ยังมีโครงสร้างข้อมูลเฉพาะแบบอื่น ๆ ที่ถูกออกแบบมาเพื่อให้สามารถค้นหาได้อย่างรวดเร็ว เช่น ตารางแฮช ซึ่งสามารถนำมาใช้ในการค้นหาข้อมูลได้มีประสิทธิภาพกว่าการค้นหาแบบทวิภาค อย่างไรก็ตาม การค้นหาแบบทวิภาคยังคงสามารถใช้แก้ปัญหาได้อย่างกว้างขวางมากกว่า เช่น การใช้ในการหาข้อมูลที่มีขนาดเล็กที่สุดหรือใหญ่ที่สุดตัวถัดไปจากค่าเป้าหมายในแถวลำดับ ถึงแม้ข้อมูลนั้นจะไม่ปรากฏในแถวลำดับก็ตาม

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

การค้นหาแบบทวิภาคจะแบ่งครึ่งชุดข้อมูลที่ต้องการค้นหา ดังนั้นจึงจัดให้การค้นหาแบบทวิภาคเป็นขั้นตอนวิธีแบ่งแยกและเอาชนะ และขั้นตอนวิธีการค้นหา

ขั้นตอนวิธี[แก้]

การค้นหาแบบทวิภาคสามารถดำเนินการได้ในแถวลำดับที่มีการเรียงลำดับข้อมูลแล้ว โดยจะเริ่มจากการเปรียบเทียบค่าของข้อมูลที่อยู่ตรงกลางของแถวลำดับกับค่าเป้าหมาย หากข้อมูลตรงกลางนั้นมีค่าเท่ากับค่าเป้าหมาย จะทำการคืนค่าตำแหน่งในแถวลำดับของข้อมูลนั้น แต่หากข้อมูลตรงกลางมีค่าน้อยกว่าค่าเป้าหมาย การค้นหาแบบทวิภาคจะถูกดำเนินการต่อไปกับแถวลำดับครึ่งหลัง ในทำนองเดียวกัน หากข้อมูลตรงกลางมีค่ามากกว่าค่าเป้าหมาย การค้นหาก็จะถูกดำเนินการในแถวลำดับครึ่งหน้า ด้วยขั้นตอนวิธีนี้ทำให้สามารถกำจัดข้อมูลได้ครึ่งหนึ่งเสมอในทุกการวนซ้ำ^[7]

การวนซ้ำ[แก้]

กำหนดให้แถวลำดับ $A$ มีสมาชิก $n$ ตัว โดยแต่ละตัวมีค่าหรือระเบียน [en] $A_{0},A_{1},A_{2},\ldots ,A_{n-1}$ ซึ่งถูกเรียงลำดับข้อมูลเพื่อให้ $A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}$ มีดัชนีของต้นแถวลำดับ $L$ และดัชนีปลายแถวลำดับ $R$ และกำหนดค่าเป้าหมาย $T$ ซับรูทีนต่อไปนี้ใช้การค้นหาแบบทวิภาคเพื่อหาดัชนีตำแหน่งของ $T$ ใน $A$ ^[7]

กำหนดให้ $L=0$ และ $R=n-1$
ถ้า $L>R$ แล้วการค้นหาจะสิ้นสุดลง และคืนค่าว่าค้นหาไม่สำเร็จ
กำหนดให้ $m$ (ตำแหน่งกึ่งกลางของแถวลำดับที่สนใจ) มีค่าเท่ากับฟังก์ชันพื้นของ ${\frac {L+R}{2}}$ หรือหมายถึงจำนวนเต็มที่มากที่สุดที่มีค่าน้อยกว่าหรือเท่ากับ ${\frac {L+R}{2}}$
ถ้า $A_{m}<T$ แล้วกำหนดให้ $L=m+1$ และกลับไปยังขั้นตอนที่ 2
ถ้า $A_{m}>T$ แล้วกำหนดให้ $R=m-1$ และกลับไปยังขั้นตอนที่ 2
ถ้า $A_{m}=T$ แสดงว่าการค้นหาเสร็จสิ้น คืนค่า $m$

ขั้นตอนการวนซ้ำนี้จะติดตามขอบเขตการค้นหาด้วยตัวแปร $L$ และ $R$ และสามารถแสดงผลในรูปรหัสเทียมได้ดังตัวอย่างด้านล่าง โดยชื่อตัวแปรที่ใช้จะคงเดิมเหมือนตัวอย่างด้านบน floor คือ ฟังก์ชันพื้น และ unsuccessful แทนค่าเฉพาะที่สื่อถึงความล้มเหลวของการค้นหา^[7]

function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m − 1
        else:
            return m
    return unsuccessful

ในอีกทางเลือกหนึ่ง ขั้นตอนวิธีนี้อาจใช้ค่าฟังก์ชันเพดานของ ${\frac {L+R}{2}}$ ซึ่งจะทำให้ผลลัพธ์เปลี่ยนแปลงไปหากค่าเป้าหมายปรากฏในแถวลำดับมากกว่า 1 ครั้ง

ขั้นตอนทางเลือก[แก้]

ในขั้นตอนวิธีด้านบนอาศัยการตรวจสอบในทุก ๆ การวนซ้ำว่าค่ากลาง ( $m$ ) มีค่าเท่ากับค่าเป้าหมายที่ต้องการ ( $T$ ) หรือไม่ กระบวนการบางอย่างได้ละเว้นวิธีการตรวจสอบนี้ในแต่ละการวนซ้ำ ทำให้ขั้นตอนวิธีนั้นจะทำการตรวจสอบนี้เฉพาะเมื่อการวนซ้ำครั้งนั้นเหลือสมาชิกเพียงตัวเดียว (เมื่อ $L=R$ ) ส่งผลให้ใช้เวลาน้อยลงในระหว่างรอบการวนซ้ำ เนื่องจากชุดเปรียบเทียบจะถูกกำจัดทิ้งหนึ่งชุดในหนึ่งรอบการวนซ้ำ ในขณะที่มีจำนวนรอบการวนซ้ำเพิ่มขึ้นเพียงหนึ่งครั้งโดยเฉลี่ยเท่านั้น^[8]

Hermann Bottenbruch [en] ได้ตีพิมพ์กระบวนการแรกที่ละเว้นวิธีการตรวจสอบนี้ในปีค.ศ. 1962^[8]^[9]

กำหนดให้ $L=0$ และ $R=n-1$
เมื่อ $L\neq R$ $L\neq R$
1. กำหนดให้ $m$ (ตำแหน่งกึ่งกลางของแถวลำดับที่สนใจ) มีค่าเท่ากับฟังก์ชันเพดานของ ${\frac {L+R}{2}}$ หรือหมายถึงจำนวนเต็มที่น้อยที่สุดที่มีค่ามากกว่าหรือเท่ากับ ${\frac {L+R}{2}}$
2. ถ้า $A_{m}>T$ แล้วกำหนดให้ $R=m-1$
3. มิฉะนั้น ถ้า $A_{m}\leq T$ แล้วกำหนดให้ $L=m$
เมื่อ $L=R$ การค้นหาจะเสร็จสิ้นลง ถ้า $A_{L}=T$ แล้วจะคืนค่า $L$ มิฉะนั้นจะคืนค่าว่าไม่สำเร็จ

เมื่อ ceil คือฟังก์ชันเพดาน รหัสเทียมของกระบวนการนี้ คือ:

function binary_search_alternative(A, n, T) is
    L := 0
    R := n − 1
    while L != R do
        m := ceil((L + R) / 2)
        if A[m] > T then
            R := m − 1
        else:
            L := m
    if A[L] = T then
        return L
    return unsuccessful

สมาชิกที่ซ้ำกัน[แก้]

การค้นหาแบบทวิภาคอาจคืนค่าดัชนีใด ๆ ของสมาชิกที่มีค่าเท่ากับค่าเป้าหมาย ถึงแม้ในแถวลำดับจะมีสมาชิกที่มีค่าซ้ำกัน ยกตัวอย่างเช่น ถ้าแถวลำดับที่ต้องการค้นหาคือ $[1,2,3,4,4,5,6,7]$ และค่าเป้าหมายคือ $4$ แล้วขั้นตอนวิธีอาจคืนค่าที่ถูกต้องได้ทั้งตำแหน่งที่ 4 (ดัชนีที่ 3) หรือตำแหน่งที่ 5 (ดัชนีที่ 4) ซึ่งกระบวนการปกติมักจะคืนค่าตำแหน่งที่ 4 (ดัชนีที่ 3) แต่ก็ไม่ใช่เสมอไปที่ค่าที่ถูกคืนจะเป็นตำแหน่งแรกของสมาชิกที่ซ้ำกัน อย่างไรก็ตาม ในบางครั้งการหาค่าเป้าหมายที่มีสมาชิกที่ซ้ำกันในแถวลำดับก็จำเป็นที่จะต้องหาสมาชิกขอบซ้ายสุดหรือขวาสุด ในตัวอย่างข้างต้น สมาชิกซ้ายสุดที่มีค่าเท่ากับ 4 คือสมาชิกตำแหน่งที่ 4 และสมาชิกขวาสุดที่มีค่าเท่ากับ 4 คือสมาชิกตำแหน่งที่ 5 ซึ่งการค้นหาโดยใช้ขั้นตอนทางเลือกจะคืนค่าดัชนีของสมาชิกขวาสุด (ถ้ามี)^[9]

กระบวนการหาสมาชิกซ้ายสุด[แก้]

ในการจะหาสมาชิกซ้ายสุดสามารถทำได้ดังนี้:^[10]

กำหนดให้ $L=0$ และ $R=n$
เมื่อ $L<R$ $L<R$
1. กำหนดให้ $m$ (ตำแหน่งกึ่งกลางของแถวลำดับที่สนใจ) มีค่าเท่ากับฟังก์ชันพื้นของ ${\frac {L+R}{2}}$ หรือหมายถึงจำนวนเต็มที่มากที่สุดที่มีค่าน้อยกว่าหรือเท่ากับ ${\frac {L+R}{2}}$
2. ถ้า $A_{m}<T$ แล้วกำหนดให้ $L=m+1$
3. มิฉะนั้น ถ้า $A_{m}\geq T$ แล้วกำหนดให้ $R=m$
คืนค่า $L$

ถ้า $L<n$ และ $A_{L}=T$ แล้ว $A_{L}$ คือสมาชิกซ้ายสุดที่มีค่าเท่ากับ $T$ ในกรณีที่ไม่มีสมาชิกใดในแถวลำดับที่มีค่าเท่ากับ $T$ $L$ จะถือว่าเป็นอันดับของ $T$ ในแถวลำดับ หรือคือจำนวนสมาชิกทั้งหมดในแถวลำดับที่มีค่าน้อยกว่า $T$

เมื่อ floor คือฟังก์ชันพื้น รหัสเทียมของกระบวนการนี้ คือ:

function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

กระบวนการหาสมาชิกขวาสุด[แก้]

ในการจะหาสมาชิกขวาสุดสามารถทำได้ดังนี้:^[10]

กำหนดให้ $L=0$ และ $R=n$
เมื่อ $L<R$ $L<R$
1. กำหนดให้ $m$ (ตำแหน่งกึ่งกลางของแถวลำดับที่สนใจ) มีค่าเท่ากับฟังก์ชันพื้นของ ${\frac {L+R}{2}}$ หรือหมายถึงจำนวนเต็มที่มากที่สุดที่มีค่าน้อยกว่าหรือเท่ากับ ${\frac {L+R}{2}}$
2. ถ้า $A_{m}>T$ แล้วกำหนดให้ $R=m$
3. มิฉะนั้น ถ้า $A_{m}\leq T$ แล้วกำหนดให้ $L=m+1$
คืนค่า $R-1$

ถ้า $R>0$ และ $A_{R}-1=T$ แล้ว $A_{R}-1$ คือสมาชิกขวาสุดที่มีค่าเท่ากับ $T$ ในกรณีที่ไม่มีสมาชิกใดในแถวลำดับที่มีค่าเท่ากับ $T$ $n-R$ จะเป็นจำนวนสมาชิกทั้งหมดในแถวลำดับที่มีค่ามากกว่ากว่า $T$

เมื่อ floor คือฟังก์ชันพื้น รหัสเทียมของกระบวนการนี้ คือ:

function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] > T:
            R := m
        else:
            L := m + 1
    return R - 1

การหาคู่ที่ใกล้เคียง[แก้]

การค้นหาแบบทวิภาคสามารถปรับปรุงเพื่อคำนวณหาคู่ที่ใกล้เคียงได้ ในตัวอย่างด้านบน อันดับ (rank) สมาชิกก่อนหน้า (predecessor) สมาชิกตามหลัง (successor) และเพื่อนบ้านใกล้สุด (nearest neighbor) ได้ถูกแสดงสำหรับค่าเป้าหมายเท่ากับ $5$ ซึ่งไม่อยู่ในแถวลำดับนี้

กระบวนการด้านต้นจะดำเนินการหาคู่ที่ถูกต้องซึ่งคือตำแหน่งของสมาชิกที่มีค่าเท่ากับค่าเป้าหมายเท่านั้น อย่างไรก็ตาม การขยายขอบเขตการค้นหาแบบทวิภาคเพื่อดำเนินการหาคู่ที่ใกล้เคียงก็สามารถทำได้โดยง่าย เพราะการค้นหาแบบทวิภาคจะดำเนินการในแถวลำดับที่เรียงลำดับแล้ว ยกตัวอย่างเช่น การค้นหาแบบทวิภาคสามารถใช้เพื่อคำนวณอันดับ (จำนวนสมาชิกที่มีค่าน้อยกว่า) สมาชิกก่อนหน้า (predecessor) สมาชิกตามหลัง (successor) และเพื่อนบ้านใกล้สุดของค่าที่กำหนด ซึ่งการหาขอบเขต [en] หรือคือการหาจำนวนสมาชิกระหว่างค่าสองค่าก็สามารถดำเนินการได้ด้วยการหาอันดับ 2 ครั้ง^[11]

การหาอันดับสามารถดำเนินการได้ด้วยกระบวนการหาสมาชิกซ้ายสุด โดยจะคืนค่าจำนวนสมาชิกที่มีค่าน้อยกว่าค่าเป้าหมาย^[11]
การหาสมาชิกก่อนหน้าสามารถดำเนินการได้ด้วยการหาอันดับ ถ้าอันดับของค่าเป้าหมายคือ $r$ แล้วอันดับของสมาชิกก่อนหน้าคือ $r-1$ ^[12]
การหาสมาชิกตามหลังสามารถดำเนินการได้ด้วยกระบวนการหาสมาชิกขวาสุด ถ้ากระบวนการนั้นคืนค่า $r$ แล้วอันดับของสมาชิกตามหลังคือ $r+1$
เพื่อนบ้านใกล้สุดของค่าเป้าหมายอาจเป็นสมาชิกก่อนหน้าหรือสมาชิกตามหลังก็ได้ ขึ้นอยู่กับว่าค่าไหนใกล้เคียงค่าเป้าหมายมากกว่ากัน
การหาขอบเขตสามารถทำได้อย่างตรงไปตรงมา^[12] โดยเมื่อรู้อันดับของค่าทั้งสอง (สมาชิกก่อนหน้าและสมาชิกตามหลัง) แล้ว จำนวนสมาชิกที่มีค่ามากกว่าหรือเท่ากับค่าสมาชิกก่อนหน้าและน้อยกว่าค่าสมาชิกตามหลังจะเป็นผลต่างระหว่างอันดับของค่าทั้งสอง การนับแบบนี้สามารถมีค่าเพิ่มขึ้นหรือลดลง 1 ค่าได้ขึ้นอยู่กับว่าจุดปลายของขอบเขตควรถูกพิจารณาเป็นส่วนหนึ่งของขอบเขตหรือไม่ และแถวลำดับมีข้อมูลที่เข้าคู่กับจุดปลายเหล่านั้นหรือไม่^[13]

ประสิทธิภาพ[แก้]

ในแง่ของจำนวนการเปรียบเทียบ ประสิทธิภาพของการค้นหาแบบทวิภาคสามารถวิเคราะห์ได้จากการดูการทำงานของต้นไม้แบบทวิภาค โดยปมรากของต้นไม้คือค่ากลางของแถวลำดับ ค่ากลางของครึ่งแถวล่างคือปมลูกด้านซ้ายของราก และค่ากลางของครึ่งแถวบนคือปมลูกด้านขวาของราก ส่วนที่เหลือของต้นไม้ก็มีโครงสร้างที่คล้ายคลึงกับรูปแบบที่กล่าวไปด้านต้น คือ เริ่มจากปมราก การตัดสินใจว่าจะผ่านต้นไม้ย่อยด้านซ้ายหรือขวาจะขึ้นอยู่กับว่า ค่าเป้าหมายมีค่าน้อยหรือมากกว่าปมที่กำลังตัดสินใจอยู่^[6]^[14]

ในกรณีที่แย่ที่สุด การค้นหาแบบทวิภาคจะถูกวนซ้ำทั้งหมด ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ รอบการเปรียบเทียบ เมื่อ ${\textstyle \lfloor \rfloor }$ คือสัญลักษณ์ที่แสดงถึงฟังก์ชันพื้นที่ให้ผลลัพธ์เป็นจำนวนเต็มที่มากที่สุดที่น้อยกว่าหรือเท่ากับอาร์กิวเมนต์ (argument) และ ${\textstyle \log _{2}}$ คือลอการิทึมฐานสอง [en] เนื่องจากกรณีที่แย่ที่สุดจะเกิดขึ้นเมื่อการค้นหาดำเนินการไปถึงชั้นล่างสุดของต้นไม้ ซึ่งต้นไม้แบบทวิภาคจะมีทั้งหมด ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ ชั้นเสมอ

กรณีที่แย่ที่สุดอาจเกิดขึ้นได้เช่นกันในกรณีที่ค่าเป้าหมายไม่อยู่ในแถวลำดับ ถ้า ${\textstyle n}$ มีค่าน้อยกว่ากำลังของสองอยู่หนึ่งค่า แล้วกรณีนี้จะเป็นจริงเสมอ มิฉะนั้น การค้นหาอาจวนซ้ำ ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ รอบเมื่อการค้นหาดำเนินการไปถึงชั้นล่างสุดของต้นไม้ อย่างไรก็ตาม หากการค้นหาสิ้นสุดที่ชั้นที่ลึกที่สุดเป็นอันดับสองของต้นไม้ แล้วการค้นหาจะวนซ้ำทั้งหมด ${\textstyle \lfloor \log _{2}(n)\rfloor }$ รอบ ซึ่งน้อยกว่าจำนวนการวนซ้ำของกรณีที่แย่ที่สุดอยู่หนึ่งครั้ง^[15]

หากสมมุติให้สมาชิกทุกตัวมีโอกาสที่จะถูกค้นหาเท่ากัน แล้วการค้นหาแบบทวิภาคจะวนซ้ำทั้งหมด $\lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n$ รอบโดยเฉลี่ย เมื่อค่าเป้าหมายมีอยู่ในแถวลำดับ ซึ่งจะประมาณเท่ากับ $\log _{2}(n)-1$ รอบ ถ้าค่าเป้าหมายไม่อยู่ในแถวลำดับ แล้วการค้นหาแบบทวิภาคจะวนซ้ำ $\lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1)$ รอบโดยเฉลี่ย โดยสมมุติให้ขอบเขตระหว่างและนอกเหนือจากสมาชิกมีโอกาสที่จะถูกค้นหาเท่ากัน^[14]

ในกรณีที่ดีที่สุด หรือเมื่อค่าเป้าหมายคือค่ากลางของแถวลำดับ ตำแหน่งของค่าเป้าหมายจะถูกคืนค่าหลังจากการวนซ้ำเพียงหนึ่งรอบ^[16]

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

ความซับซ้อนด้านพื้นที่[แก้]

การค้นหาแบบทวิภาคจำเป็นต้องใช้พอยน์เตอร์ (pointer) 3 อันในการเก็บตำแหน่งที่อยู่ของตัวแปร โดยอาจเป็นดัชนีของแถวลำดับ หรือพอยน์เตอร์ไปยังตำแหน่งที่อยู่หน่วยความจำ โดยไม่คำนึงถึงขนาดของแถวลำดับ ดังนั้น ความซับซ้อนด้านพื้นที่ของการค้นหาแบบทวิภาคคือ $O(1)$ ในรูปแบบการคำนวณ word RAM [en]

แหล่งที่มาของกรณีเฉลี่ย[แก้]

จำนวนการวนซ้ำโดยเฉลี่ยของการค้นหาแบบทวิภาคขึ้นอยู่กับความน่าจะเป็นที่สมาชิกแต่ละตัวในแถวลำดับจะถูกค้นหา กรณีเฉลี่ยจะแตกต่างกันไปสำหรับการค้นหาที่สำเร็จและไม่สำเร็จ สำหรับการค้นหาที่สำเร็จจะถูกอนุมานว่าสมาชิกแต่ละตัวในแถวลำดับมีโอกาสที่จะถูกค้นหาเท่ากัน สำหรับการค้นหาที่ไม่สำเร็จจะถูกอนุมานว่าช่วงระหว่างและนอกเหนือจากสมาชิกมีโอกาสที่จะถูกค้นหาเท่ากัน กรณีเฉลี่ยสำหรับการค้นที่สำเร็จคือจำนวนการวนซ้ำเพื่อค้นหาสมาชิกทุกตัวในครั้งเดียว หารด้วย $n$ ซึ่งก็คือจำนวนสมาชิกในแถวลำดับ ส่วนกรณีเฉลี่ยสำหรับการค้นหาที่ไม่สำเร็จคือจำนวนการวนซ้ำเพื่อค้นหาสมาชิกในทุกช่วงในครั้งเดียว หารด้วยจำนวน $n+1$ ช่วง^[14]

การค้าหาที่สำเร็จ[แก้]

ในต้นไม้แบบทวิภาค การค้นหาที่สำเร็จสามารถถูกอธิบายได้ด้วยเส้นทางจากรากถึงปมเป้าหมาย เรียกว่า เส้นทางภายใน (internal path) ความยาวของเส้นทางจะเท่ากับจำนวนขอบ (เส้นเชื่อมต่อระหว่างปม) ที่เส้นทางเดินทางผ่าน เมื่อกำหนดให้เส้นทางที่สอดคล้องนั้นมีความยาว $l$ จำนวนการวนซ้ำในการค้นจะเท่ากับ $l+1$ โดยนับการวนซ้ำรอบแรกด้วย ความยาวของเส้นทางภายในจะเท่ากับผลรวมของความยาวของเส้นทางภายในที่เฉพาะ เนื่องจากจะมีเพียงหนึ่งเส้นทางที่เดินทางจากรากไปยังปมเดี่ยวใด ๆ ดังนั้น เส้นทางภายในแต่ละเส้นจะเป็นตัวแทนของการค้นหาสมาชิกแต่ละตัวโดยเฉพาะ ถ้ามีสมาชิกทั้งหมด $n$ ตัว (ซึ่ง $n$ จะเป็นจำนวนเต็มบวก) และความยาวของเส้นทางภายในคือ $I(n)$ แล้วจำนวนการวนซ้ำโดยเฉลี่ยสำหรับการค้นหาที่สำเร็จคือ $T(n)=1+{\frac {I(n)}{n}}$ โดยจำนวนการวนซ้ำ 1 ครั้งที่ถูกบวกเข้าไปเพิ่มคือการวนซ้ำครั้งแรก^[14]

เนื่องจากการค้นหาแบบทวิภาคคือขั้นตอนวิธีที่ดีที่สุดในการค้นหาแบบเปรียบเทียบ ปัญหานี้จะถูกลดลงเหลือเพียงการคำนวณความยาวของเส้นทางภายในที่น้อยที่สุดของต้นไม้แบบทวิภาคทั้งหมดที่มีปม $n$ ปม ซึ่งจะเท่ากับ:^[17]

$I(n)=\sum _{k=1}^{n}\left\lfloor \log _{2}(k)\right\rfloor$

ตัวอย่างเช่น ในแถวลำดับที่มีสมาชิก 7 ตัว หากค่าเป้าหมายคือราก การค้นหาจะต้องใช้การวนซ้ำหนึ่งครั้ง หากเป็นสมาชิกที่อยู่ล่างรากหนึ่งชั้นจะต้องใช้การวนซ้ำสองครั้ง และสมาชิกสี่ตัวล่างสุดจะต้องใช้การวนซ้ำสามครั้ง ในกรณีนี้ ความยาวของเส้นทางภายในคือ:^[17]

$\sum _{k=1}^{7}\left\lfloor \log _{2}(k)\right\rfloor =0+2(1)+4(2)=2+8=10$

จากสมการการคำนวณกรณีเฉลี่ย จำนวนการวนซ้ำโดยเฉลี่ยจะเท่ากับ $1+{\frac {10}{7}}=2{\frac {3}{7}}$ และผลรวม $I(n)$ สามารถเขียนให้อยู่ในรูปอย่างง่ายได้ดังนี้:^[14]

$I(n)=\sum _{k=1}^{n}\left\lfloor \log _{2}(k)\right\rfloor =(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2$

แทนค่าสมการ $I(n)$ ในสมการ $T(n)$ :^[14]

$T(n)=1+{\frac {(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2}{n}}=\lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n$

สำหรับจำนวนเต็ม $n$ สมการด้านบนนี้คือสมการของกรณีเฉลี่ยสำหรับการค้นหาที่สำเร็จ

การค้าหาที่ไม่สำเร็จ[แก้]

การค้นหาที่ไม่สำเร็จสามารถถูกอธิบายได้โดยการแผ่ขยายต้นไม้ด้วยปมภายนอก (external nodes) ซึ่งจะเกิดเป็นต้นไม้ทวิภาคแบบแผ่ขยาย (extended binary tree) ถ้าปมภายในหรือปมที่ปรากฏในต้นไม้มีปมลูกน้อยกว่า 2 ปม แล้วปมลูกเพิ่มเติมหรือปมภายนอกจะถูกเพิ่มในต้นไม้เพื่อให้ปมภายในแต่ละปมมีปมลูกครบ 2 ปม ด้วยวิธีการนี้แล้วจะทำให้การค้นหาที่ไม่สำเร็จสามารถถูกอธิบายได้ด้วยเส้นทางไปยังปมภายนอกที่มีพ่อแม่เป็นปมเดี่ยวเดียวที่มีอยู่ในการวนซ้ำครั้งสุดท้าย เส้นทางภายนอกคือเส้นทางจากรากสู่ปมภายนอก ซึ่งความยาวของเส้นทางภายนอกนั้นจะเท่ากับผลรวมของความยาวของเส้นทางภายนอกที่เฉพาะ ถ้ามีสมาชิกทั้งหมด $n$ ตัว (ซึ่ง $n$ จะเป็นจำนวนเต็มบวก) และความยาวของเส้นทางภายนอกคือ $E(n)$ แล้วจำนวนการวนซ้ำโดยเฉลี่ยสำหรับการค้นหาที่ไม่สำเร็จคือ $T'(n)={\frac {E(n)}{n+1}}$ โดยจำนวนการวนซ้ำ 1 ครั้งที่ถูกบวกเข้าไปเพิ่มคือการวนซ้ำครั้งแรก สมการความยาวของเส้นทางภายนอกถูกหารด้วย $n+1$ แทนที่จะเป็น $n$ เพราะมีเส้นทางภายนอกทั้งหมด $n+1$ เส้น ซึ่งคือช่วงระหว่างและนอกเหนือจากสมาชิกในแถวลำดับ^[14]

เช่นเดียวกับการค้นหาที่สำเร็จ ปัญหานี้จะถูกลดลงเหลือเพียงการคำนวณความยาวของเส้นทางภายนอกที่น้อยที่สุดของต้นไม้แบบทวิภาคทั้งหมดที่มีปม $n$ ปม สำหรับต้นไม้แบบทวิภาคทั้งหมด ความยาวของเส้นทางภายนอกเท่ากับความยาวของเส้นทางภายในบวกด้วย $2n$ ^[17] แทนค่าสมการ $I(n)$ :^[14]

$E(n)=I(n)+2n=\left[(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2\right]+2n=(n+1)(\lfloor \log _{2}(n)\rfloor +2)-2^{\lfloor \log _{2}(n)\rfloor +1}$

แทนค่าสมการ $E(n)$ ในสมการ $T'(n)$ สมการของกรณีเฉลี่ยสำหรับการค้นหาที่ไม่สำเร็จคือ:^[14]

$T'(n)={\frac {(n+1)(\lfloor \log _{2}(n)\rfloor +2)-2^{\lfloor \log _{2}(n)\rfloor +1}}{(n+1)}}=\lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1)$

ประสิทธิภาพของขั้นตอนทางเลือก[แก้]

ในการวนซ้ำแต่ละครั้งของขั้นตอนการค้นหาแบบทวิภาคด้านบนจะมีการเปรียบเทียบหนึ่งหรือสองครั้ง คือการเปรียบเทียบว่าค่าตรงกลางเท่ากับค่าเป้าหมายหรือไม่ในแต่ละการวนซ้ำ สมมุติให้สมาชิกแต่ละตัวในแถวลำดับมีโอกาสที่จะถูกค้นหาเท่ากัน การวนซ้ำแต่ละครั้งจะมีการเปรียบเทียบทั้งหมด 1.5 ครั้งโดยเฉลี่ย ตัวแปรของขั้นตอนวิธีจะตรวจสอบว่าค่าตรงกลางมีค่าเท่ากับค่าเป้าหมายหรือไม่ในตอนท้ายของการค้นหา ซึ่งทำให้ตัวเปรียบเทียบถูกกำจัดทิ้งไปครึ่งหนึ่งโดยเฉลี่ยในแต่ละการวนซ้ำ สิ่งนี้จะช่วยลดเวลาที่ใช้ในการค้นหาต่อจำนวนการวนซ้ำหนึ่งรอบในคอมพิวเตอร์ส่วนมาก อย่างไรก็ตาม การค้นหานี้จะมีจำนวนการวนซ้ำมากที่สุดอย่างแน่นอน โดยเฉลี่ยแล้วจำนวนการวนซ้ำจะเพิ่มขึ้นหนึ่งครั้ง แต่เนื่องจากการวนเปรียบเทียบจะทำทั้งหมด ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ ครั้งในกรณีที่แย่ที่สุด ประสิทธิภาพที่เพิ่มขึ้นเล็กน้อยในแต่ละการวนซ้ำจึงไม่สามารถทดแทนจำนวนการวนซ้ำที่เพิ่มขึ้นได้ (ยกเว้นในกรณีที่ $n$ มีค่ามาก ๆ)^[c]^[18]^[19]

ระยะเวลาดำเนินการและแคชที่ใช้[แก้]

ในการวิเคราะห์ประสิทธิภาพของการค้นหาแบบทวิภาคจะต้องพิจารณาระยะเวลาที่ใช้ในการเปรียบเทียบสมาชิกสองตัว สำหรับจำนวนเต็มและสตริง (string) ระยะเวลาที่ใช้ในการดำเนินการจะเพิ่มขึ้นแปรผันตรงกับความยาวของการเข้ารหัสสมาชิกหรือก็คือจำนวนบิตของสมาชิก ตัวอย่างเช่น การเปรียบเทียบคู่ของจำนวนเต็มเฉพาะค่าบวกขนาด 64 บิทจะอาศัยการเปรียบเทียบเป็นสองเท่าของการเปรียบเทียบคู่ของจำนวนเต็มเฉพาะค่าบวกขนาด 32 บิท กรณีที่แย่ที่สุดจะเกิดขึ้นเมื่อจำนวนเต็มทั้งสองมีค่าเท่ากัน ซึ่งระยะเวลาดำเนินการนี้จะยิ่งมากอย่างมีนัยสำคัญเมื่อความยาวของการเข้ารหัสสมาชิกมีค่ามาก เช่น การเปรียบเทียบข้อมูลชนิดจำนวนเต็มขนาดใหญ่หรือสตริงแบบยาว ซึ่งจะทำให้การเปรียบเทียบข้อมูลมีราคาแพง นอกจากนั้น การเปรียบเทียบค่าของจำนวนจุดลอยตัว (การแทนจำนวนจริงแบบดิจิทัลที่พบเห็นบ่อยที่สุด) จะแพงกว่าการเปรียบเทียบจำนวนเต็มและสตริงแบบสั้น

ในสถาปัตยกรรมคอมพิวเตอร์ส่วนมาก หน่วยประมวลผลกลางจะมีแคชของฮาร์ดแวร์แยกจากแรม เนื่องจากอยู่ในหน่วยประมวลผลกลาง แคชจะเข้าถึงได้รวดเร็วกว่าแต่ก็กักเก็บข้อมูลได้น้อยกว่าแรม ดังนั้น หน่วยประมวลผลกลางส่วนมากจะกักเก็บตำแหน่งหน่วยความจำ (memory location) ที่ถูกเข้าถึงเมื่อไม่นานมานี้และที่อยู่ใกล้เคียงกัน ยกตัวอย่างเช่น เมื่อเข้าถึงสมาชิกของแถวลำดับ สมาชิกนั้นอาจถูกกักเก็บควบคู่ไปกับสมาชิกที่อยู่ใกล้เคียงกับมันในแรม ทำให้สามารถเข้าถึงสมาชิกที่มีดัชนีใกล้เคียงกัน (locality of reference [en]) ได้อย่างรวดเร็ว ในแถวลำดับที่มีการเรียงลำดับแล้ว การค้นหาแบบทวิภาคสามารถกระโดดไปยังตำแหน่งหน่วยความจำที่อยู่ไกลได้ถ้าแถวลำดับนั้นมีขนาดใหญ่ ต่างจากขั้นตอนวิธีอื่น เช่น การค้นหาเชิงเส้น [en] และการตรวจสอบเชิงเส้น [en] ในตารางแฮช ซึ่งเข้าถึงสมาชิกได้ตามลำดับเท่านั้น ในระบบส่วนใหญ่ สิ่งนี้อาจเพิ่มระยะเวลาดำเนินการของการค้นหาแบบทวิภาคในแถวลำดับขนาดใหญ่ได้เล็กน้อย^[20]

การค้าหาแบบทวิภาคเปรียบเทียบกับการค้นหาแบบอื่น[แก้]

การใช้การค้นหาแบบทวิภาคในการดำเนินการเพิ่มและลบสมาชิกในแถวลำดับที่มีการเรียงลำดับไว้แล้วนับเป็นวิธีการที่ไม่มีประสิทธิภาพ เนื่องจากใช้เวลาถึง $O(n)$ ในการดำเนินการแต่ละครั้ง นอกจากนั้นแล้ว แถวลำดับที่มีการเรียงลำดับแล้วยังมีการใช้หน่วยความจำที่ซับซ้อน โดยเฉพาะเมื่อสมาชิกถูกเพิ่มเข้าไปในแถวลำดับบ่อย ๆ ^[21] ดังนั้นจึงมีโครงสร้างข้อมูลอื่น ๆ ที่สามารถดำเนินการเพิ่มและลบได้มีประสิทธิภาพมากกว่า การค้นหาแบบทวิภาคสามารถใช้เพื่อการดำเนินการหาคู่ที่ถูกต้องและการตรวจสอบการเป็นสมาชิกของเซต (ตรวจสอบว่าค่าเป้าหมายอยู่ในกลุ่มสมาชิกข้อมูลหรือไม่) ซึ่งถึงแม้โครงสร้างข้อมูลอื่น ๆ จะสามารถดำเนินการหาคู่ที่ถูกต้องและตรวจสอบการเป็นสมาชิกของเซตได้รวดเร็วกว่าการค้นหาแบบทวิภาค แต่การค้นหาแบบทวิภาคสามารถใช้หาคู่ที่ใกล้เคียงได้อย่างมีประสิทธภาพในขณะที่การค้นหาแบบอื่น ๆ ไม่สามารถทำได้ ซึ่งการค้นหาแบบทวิภาคใช้เวลา ${\textstyle O(\log n)}$ โดยไม่คำนึงถึงชนิดของโครงสร้างข้อมูล^[22] นอกจากนั้น ยังมีการดำเนินการบางอย่าง เช่น การหาค่าที่มากและน้อยที่สุด ที่สามารถดำเนินการได้อย่างมีประสิทธิภาพในแถวลำดับที่มีการเรียงลำดับแล้ว^[11]

การค้นหาเชิงเส้น[แก้]

การค้นหาเชิงเส้น [en] เป็นขั้นตอนวิธีการค้นหาที่เรียบง่าย โดยจะใช้วิธีการตรวจสอบข้อมูลทุก ๆ ตัวจนกว่าจะเจอค่าเป้าหมาย การค้นหาเชิงเส้นสามารถทำได้ในรายการโยง (linked list) ซึ่งสามารถดำเนินการเพิ่มหรือลบสมาชิกได้รวดเร็วกว่าแถวลำดับ การค้นหาแบบทวิภาคดำเนินการการค้นหาในแถวลำดับได้รวดเร็วกว่าการค้นหาเชิงเส้น (ยกเว้นแถวลำดับที่มีขนาดสั้น) แต่แถวลำดับนั้นจะต้องมีการเรียงลำดับมาก่อน^[d]^[24] ขั้นตอนวิธีการเรียงลำดับทั้งหมดมีพื้นฐานมาจากการเปรียบเทียบค่าของสมาชิก เช่น ควิกซอร์ต และการเรียงลำดับแบบผสาน ซึ่งใช้การเปรียบเทียบทั้งหมด ${\textstyle O(n\log n)}$ ในกรณีที่แย่ที่สุด^[25] การค้นหาแบบทวิภาคสามารถใช้หาคู่ที่ใกล้เคียงได้อย่างมีประสิทธภาพในขณะที่การค้นหาเชิงเส้นไม่สามารถทำได้ นอกจากนั้น การดำเนินการ เช่น การหาสมาชิกที่มีค่ามากและน้อยที่สุด สามารถทำได้อย่างมีประสิทธิภาพในแถวลำดับที่มีการเรียงลำดับแล้วเท่านั้น^[26]

ต้นไม้[แก้]

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

อย่างไรก็ตาม ต้นไม้ค้นหาแบบทวิภาคมักจะมีความไม่สมดุลระหว่างสองข้าง ทำให้มีประสิทธิภาพในการค้นหาน้อยกว่าการค้นหาแบบทวิภาคเล็กน้อย สิ่งนี้ยังนำไปใช้ได้กับต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้ หรือคือต้นไม้ค้นหาแบบทวิภาคที่สามารถทำให้ปมของตนเองมีความสมดุลได้ เพราะ ต้นไม้ที่มีจำนวนชั้นน้อยที่สุดเท่าที่จะเป็นไปได้แทบจะไม่ถูกสร้างขึ้นมาเลย นอกเหนือจากต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้แล้ว ต้นไม้มักจะมีความไม่สมดุลอย่างรุนแรงเนื่องจากมีจำนวนปมภายในที่มีปมลูกครบสองปมน้อยมาก ทำให้ระยะเวลาในการค้นหาโดยเฉลี่ยและในกรณีที่แย่ที่สุดใกล้เคียงกับเวลาที่ใช้ในกรณีที่มีการเปรียบเทียบ $n$ ครั้ง^[e] นอกจากนั้นต้นไม้ค้นหาแบบทวิภาคยังใช้พื้นที่เก็บข้อมูลมากกว่าแถวลำดับที่เรียงลำดับแล้ว^[29]

ต้นไม้ค้นหาแบบทวิภาคจะยืมหน่วยความจำภายนอกของฮาร์ดดิสก์เพื่อใช้ในการค้นหาแบบรวดเร็วเนื่องจากต้นไม้ค้นหาแบบทวิภาคสามารถจัดโครงสร้างในระบบแฟ้มข้อมูลได้ ซึ่งต้นไม้แบบบีคือการสรุปวิธีการการจัดระเบียบต้นไม้นี้ โดยต้นไม้แบบบีมักถูกใช้ในการจัดระเบียบพื้นที่จัดเก็บข้อมูลระยะยาว เช่น ฐานข้อมูล และแฟ้มข้อมูล^[30]^[31]

แฮชชิง[แก้]

โดยปกติแล้วสำหรับการใช้แถวลำดับแบบจับคู่ ตารางแฮช ซึ่งคือโครงสร้างข้อมูลที่เชื่อมโยงคีย์กับระเบียน [en] โดยใช้ฟังก์ชันแฮช จะสามารถนำแถวลำดับแบบจับคู่ไปใช้ได้รวดเร็วกว่าการค้นหาแบบทวิภาคในแถวลำดับระเบียนที่มีการเรียงลำดับแล้ว^[32] การใช้ตารางแฮชส่วนมากใช้เวลาโดยเฉลี่ยแบบถัวเฉลี่ย^[f]^[34] อย่างไรก็ตาม แฮชชิงไม่สามารถใช้ในการหาคู่ที่ใกล้เคียง เช่น การคำนวณหาค่าที่น้อยที่สุดตัวถัดไป ค่าที่มากที่สุดตัวถัดไป และคีย์ที่ใกล้เคียงที่สุดได้ เนื่องจากหากการค้นหาไม่สำเร็จจะมีการคืนค่าได้เพียงว่าค่าเป้าหมายนั้นไม่มีอยู่ในระเบียนใด ๆ ^[35] ดังนั้น การค้นหาแบบทวิภาคจึงถือเป็นวิธีการที่ดีที่สุดสำหรับการหาคู่ประเภทนั้น เนื่องจากใช้เวลาในรูปฟังก์ชันลอการิทึมเท่านั้น นอกจากนั้น การดำเนินการบางอย่าง เช่น การหาสมาชิกที่มีค่ามากหรือน้อยที่สุด สามารถทำได้อย่างมีประสิทธิภาพในแถวลำดับที่มีการเรียงลำดับแล้ว แต่ไม่สามารถทำได้ในตารางแฮช ^[22]

ขั้นตอนวิธีการตรวจสอบการเป็นสมาชิกของเซต[แก้]

ปัญหาที่เกี่ยวข้องกับการค้นหาคือ การตรวจสอบการเป็นสมาชิกของเซต ขั้นตอนวิธีที่มีฟังก์ชันการค้นหา เช่น การค้นหาแบบทวิภาค สามารถนำมาใช้ในการตรวจสอบการเป็นสมาชิกของเซตได้ นอกจาการค้นหาแบบทวิภาคแล้วยังมีขั้นตอนวิธีอื่น ๆ ที่เหมาะสมกับการตรวจสอบการเป็นสมาชิกของเซตโดยเฉพาะมากกว่า แถวลำดับบิต [en] คือโครงสร้างข้อมูลที่เรียบง่ายและเป็นประโยชน์ดีสุดเมื่อขอบเขตของคีย์มีจำกัด โดยแถวลำดับบิตจะเก็บข้อมูลโดยใช้พื้นที่น้อยที่สุดในรูปแบบของบิต ซึ่งบิตแต่ละตัวก็จะเป็นตัวแทนของคีย์แต่ละตัวในขอบเขตของคีย์ แถวลำดับบิตมีการดำเนินการที่รวดเร็วมาก โดยใช้เวลาเพียง $O(1)$ เท่านั้น ^[36] นอกจากแถวลำดับบิตแล้ว Judy1 ของแถวลำดับจูดี้ก็ยังสามารถจัดเก็บคีย์ขนาด 64 บิตได้อย่างมีประสิทธิภาพ^[37]

สำหรับผลลัพธ์ที่ใกล้เคียง ตัวกรองของบลูม หรือคือโครงสร้างข้อมูลที่เกี่ยวกับความเป็นไปได้ซึ่งอาศัยการแฮชชิง จะกักเก็บเซตของคีย์โดยการเข้ารหัสคีย์ซึ่งจะอาศัยแถวลำดับบิต [en] และฟังก์ชันแฮชหลายฟังก์ชัน ส่วนมากแล้ว ตัวกรองของบลูมจะใช้พื้นที่กักเก็บข้อมูลน้อยกว่าแถวลำดับบิตในขณะที่ก็ใช้เวลาดำเนินการไม่ได้นานกว่า โดยหากอาศัยฟังก์ชันแฮชทั้งหมด $k$ ฟังก์ชัน การตรวจสอบการเป็นสมาชิกของเซตจะใช้เวลาดำเนินการเพียง $O(k)$ เท่านั้น อย่างไรก็ตาม ตัวกรองของบลูมยังคงมีปัญหาเรื่องผลบวกลวงอยู่ ^[g]^[h]^[39]

โครงสร้างข้อมูลอื่น[แก้]

ยังมีโครงสร้างข้อมูลอื่น ๆ อีกที่มีการปรับปรุงจากการค้นหาแบบทวิภาคทั้งในด้านการค้นหาและการดำเนินการอื่น ๆ ที่สามารถทำได้ในแถวลำดับที่มีการเรียงลำดับแล้ว ตัวอย่างเช่น โครงสร้างข้อมูลแบบเฉพาะด้าน เช่น Van Emde Boas tree [en] ต้นไม้ฟิวชัน [en] และแถวลำดับบิต [en] สามารถดำเนินการค้นหา การหาคู่ที่ใกล้เคียง และการดำเนินการอื่น ๆ ที่สามารถทำได้ในแถวลำดับที่มีการเรียงลำดับแล้ว ได้อย่างมีประสิทธิภาพมากกว่าการค้นหาแบบทวิภาค โครงสร้างข้อมูลแบบเฉพาะด้านเหล่านี้สามารถดำเนินการได้รวดเร็วกว่า เพราะใช้ประโยชน์จากคุณสมบัติของคีย์ที่มีแอททริบิวต์ (attribute) บางอย่าง (โดยปกติจะเป็นคีย์ที่เป็นจำนวนเต็มที่มีขนาดเล็ก) ดังนั้นสำหรับคีย์ที่ไม่มีแอททริบิวต์เหล่านั้นก็จะทำให้ใช้เวลาและพื้นที่จัดเก็บข้อมูลมากขึ้น^[22] ตราบใดที่คีย์นั้นสามารถจัดลำดับได้ การดำเนินการเหล่านี้ก็สามารถดำเนินการได้โดยไม่ต้องคำนึงถึงคีย์ ซึ่งจะมีประสิทธิภาพอย่างต่ำเทียบเท่ากับประสิทธิภาพในแถวลำดับที่มีการเรียงลำดับไว้แล้ว โครงสร้างข้อมูลบางอย่าง เช่น แถวลำดับจูดี้ สามารถใช้วิธีการหลายอย่างร่วมกันเพื่อลดปัญหาที่ได้กล่าวไปในขณะที่ก็ยังคงประสิทธิภาพและความสามารถในการดำเนินการหาคู่ที่ใกล้เคียงไว้อยู่^[37]

การค้นหาแบบอื่น[แก้]

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

การค้นหาแบบทวิภาคอย่างมีเอกรูปจะเก็บค่าผลต่างระหว่างดัชนีของค่ากลางในการวนซ้ำครั้งปัจจุบันและดัชนีของค่ากลางในการวนซ้ำครั้งต่อไป ซึ่งต่างจากการค้นหาแบบทวิภาคที่เก็บค่าดัชนีของขอบเขตบนและล่าง โดยตารางค้นหา [en] ที่เก็บค่าผลต่างนี้จะถูกคำนวณไว้ล่วงหน้า ตัวอย่างเช่น ถ้าแถวลำดับที่กำลังถูกค้นหาคือ $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]$ แล้วค่ากลาง ( $m$ ) คือ $6$ ในขณะที่ค่ากลางของแถวลำดับย่อยฝั่งซ้ายหรือ ( $[1, 2, 3, 4, 5]$ ) คือ $3$ และค่ากลางของแถวลำดับย่อยฝั่งขวาหรือ ( $[7, 8, 9, 10, 11]$ ) คือ $9$ การค้นหาแบบทวิภาคอย่างมีเอกรูปจะเก็บค่า $3$ เนื่องจากดัชนีค่ากลางตัวต่อไปทั้งสองต่างก็มีผลต่างกับ $6$ เท่ากัน^[40] เพื่อที่จะลดพื้นที่ที่ใช้ในการค้นหา ขั้นตอนวิธีจะบวกหรือลบผลต่างดังกล่าวจากดัชนีของค่ากลางตัวปัจจุบัน การค้นหาแบบทวิภาคอย่างมีเอกรูปอาจดำเนินการได้รวดเร็วเมื่อถูกใช้ในระบบที่ไม่สามารถคำนวณค่ากลางได้อย่างมีประสิทธิภาพนัก เช่น ในคอมพิวเตอร์แบบทศนิยม [en] ^[41]

การค้นหาแบบเอกซ์โพเนนเชียล[แก้]

การค้นหาแบบเอกซ์โพเนนเชียลขยายขอบเขตจากการค้นหาแบบทวิภาคทำให้สามารถดำเนินการได้ในรายการที่ไม่จำกัดขอบเขต โดยจะเริ่มต้นจากการค้นหาสมาชิกตัวแรกที่ดัชนีอยู่ในรูปกำลังของสองและมีค่ามากกว่าค่าเป้าหมาย จากนั้นจึงกำหนดดัชนีของค่านั้นให้เป็นขอบเขตบน และเริ่มดำเนินการค้นหาแบบทวิภาค การค้นหาสมาชิกตัวแรกที่ตรงตามเงื่อนไขจะมีการวนซ้ำทั้งหมด ${\textstyle \lfloor \log _{2}x+1\rfloor }$ ครั้ง ก่อนที่จะเริ่มการค้นหาแบบทวิภาคซึ่งจะมีการวนซ้ำสูงสุด ${\textstyle \lfloor \log _{2}x\rfloor }$ ครั้ง เมื่อ $x$ คือตำแหน่งของค่าเป้าหมาย การค้นหาแบบเอกซ์โพเนนเชียลสามารถทำงานได้ในรายการที่มีการจำกัดขอบเขตเช่นกัน แต่จะมีประสิทธิภาพดีกว่าการค้นหาแบบทวิภาคก็ต่อเมื่อค่าเป้าหมายอยู่ใกล้กับบริเวณเริ่มต้นของแถวลำดับ^[42]

การค้นหาโดยการประมาณช่วง[แก้]

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

ฟังก์ชันการประมาณช่วงที่นิยมใช้กัน คือ การประมาณค่าในช่วงเชิงเส้น [en] กำหนดให้ $A$ คือแถวลำดับ $L,R$ คือขอบเขตล่างและขอบเขตบนตามลำดับ และ $T$ คือค่าเป้าหมาย จะได้ว่าค่าเป้าหมายจะอยู่ห่างจาก $L$ และ $R$ เป็นระยะประมาณ $(T-A_{L})/(A_{R}-A_{L})$ เมื่อใช้การประมาณค่าในช่วงเชิงเส้นในแถวลำดับที่มีการแจกแจงของสมาชิกแบบเอกรูปหรือใกล้เคียงกับเอกรูป การค้นหาโดยการประมาณช่วงจะทำการเปรียบเทียบทั้งหมด ${\textstyle O(\log \log n)}$ ครั้ง^[43]^[44]^[45]

ในการทำงานจริง การค้นหาโดยการประมาณช่วงจะดำเนินการช้ากว่าการค้นหาแบบทวิภาคในแถวลำดับที่มีขนาดเล็ก เนื่องจากการค้นหาโดยการประมาณช่วงจะต้องมีการคำนวณเพิ่มเติม แต่เมื่อขนาดแถวลำดับเพิ่มขึ้น อัตราการเพิ่มขึ้นของความซับซ้อนของเวลาในการค้นหาโดยการประมาณช่วงจะช้ากว่าการค้นหาแบบทวิภาค อย่างไรก็ตาม สิ่งนี้สามารถชดเชยได้ในกรณีที่แถวลำดับมีขนาดใหญ่มากเท่านั้น^[43]

การเรียงซ้อนแบบเศษส่วน[แก้]

การเรียงซ้อนแบบเศษส่วน คือเทคนิคที่ใช้ในการเพิ่มความเร็วในการค้นหาแบบทวิภาคสำหรับข้อมูลที่มีค่าเดียวกันในหลายแถวลำดับที่มีการเรียงลำดับแล้ว การค้นหาแยกกันในแต่ละแถวลำดับจะใช้เวลา ${\textstyle O(k\log n)}$ เมื่อ $k$ คือจำนวนแถวลำดับทั้งหมด การเรียงซ้อนแบบเศษส่วนจะลดเวลาการดำเนินการนั้นเหลือเพียง ${\textstyle O(k+\log n)}$ โดยอาศัยการเก็บข้อมูลเกี่ยวกับสมาชิกแต่ละตัวและตำแหน่งของมันในแถวลำดับอื่นลงไปในแถวลำดับแต่ละอัน^[46]^[47]

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

การประยุกต์ใช้ในกราฟ[แก้]

การค้นหาแบบทวิภาคถูกนำมาใช้กับกราฟบางประเภท โดยค่าเป้าหมายนั้นจะถูกเก็บในรูปของโหนดแทนสมาชิกในแถวลำดับ ต้นไม้ค้นหาแบบทวิภาคคือหนึ่งในตัวอย่างนั้น เมื่อโหนดของต้นไม้ถูกตรวจสอบ ขั้นตอนวิธีจะได้รู้ว่าโหนดนั้นคือเป้าหมายหรือไม่ หรือค่าเป้าหมายจะอยู่ในต้นไม้ย่อยต้นไหน อย่างไรก็ตาม การค้นหาแบบทวิภาคสามารถนำไปใช้ได้ในกราฟอื่นได้อีก เช่น ในกราฟแบบไม่มีทิศทางและถ่วงน้ำหนักเชิงบวก (an undirected, positively weighted graph) ขั้นตอนวิธีจะทราบจากการตรวจสอบโหนดใด ๆ ว่า โหนดนั้นมีค่าเท่ากับค่าเป้าหมายหรือไม่ ถ้าไม่แล้วเส้นเชื่อม (incident edge) ใดที่เป็นเส้นทางที่สั้นที่สุดจากโหนดที่กำลังตรวจสอบอยู่ไปยังโหนดเป้าหมาย เช่นเดียวกัน ต้นไม้ค้นหาแบบทวิภาคจะพิจารณาเส้นเชื่อมไปยังต้นไม้ย่อยฝั่งซ้ายและฝั่งขวาเมื่อโหนดที่กำลังตรวจสอบอยู่มีค่าไม่เท่ากับค่าเป้าหมาย สำหรับกราฟแบบไม่มีทิศทางและถ่วงน้ำหนักเชิงบวกทุกกราฟ ในกรณีที่แย่ที่สุด ขั้นตอนวิธีจะใช้การตรวจสอบทั้งหมด $O(\log n)$ ครั้งจนกว่าจะเจอโหนดเป้าหมาย^[48]

Noisy binary search[แก้]

ขั้นตอนวิธีของ Noisy binary search ถูกใช้แก้ปัญหาในกรณีที่ขั้นตอนวิธีไม่สามารถเปรียบเทียบค่าของสมาชิกในแถวลำดับได้อย่างน่าเชื่อถือ ในการเปรียบเทียบแต่ละคู่สมาชิกนั้นมีโอกาสที่ขั้นตอนวิธีจะเปรียบเทียบได้ผลลัพธ์ที่ไม่ถูกต้อง Noisy binary search สามารถค้นหาตำแหน่งที่ถูกต้องของเป้าหมายได้โดยมีความน่าจะเป็นที่ควบคุมความน่าเชื่อถือของผลลัพธ์ที่ได้ ทุก ๆ Noisy binary search จะต้องมีการเปรียบเทียบอย่างน้อย $(1-\tau ){\frac {\log _{2}(n)}{H(p)}}-{\frac {10}{H(p)}}$ ครั้งโดยเฉลี่ย โดยที่ $H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)$ คือ binary entropy function [en] และ $\tau$ คือ ความน่าจะเป็นที่กระบวนการนั้นจะคืนค่าตำแหน่งเป้าหมายที่ไม่ถูกต้อง^[49]^[50]^[51] ปัญหา noisy binary search เช่น เกมของอุลาม [en] ^[52] คือการถามคำถามยี่สิบข้อ [en] ที่แตกต่างกันเพื่อทายวัตถุหรือตัวเลขนั้น โดยคำตอบที่ได้รับจากคำถามนั้นอาจไม่ใช่คำตอบที่ถูกต้อง^[53]

การค้นหาแบบทวิภาคควอนตัม[แก้]

การดำเนินการค้นหาแบบทวิภาคในคอมพิวเตอร์แบบดั้งเดิมจะใช้การวนซ้ำทั้งหมด ${\textstyle \lfloor \log _{2}n+1\rfloor }$ ครั้งในกรณีที่แย่ที่สุด ขั้นตอนวิธีควอนตัม [en]สำหรับการค้นหาแบบทวิภาคจะมีการตรวจสอบทั้งหมด ${\textstyle \log _{2}n}$ ครั้ง (แทนจำนวนการวนซ้ำในกระบวนการดั้งเดิม) แต่ตัวประกอบคงที่ (constant factor) จะมีค่าน้อยกว่าหนึ่ง ทำให้มีค่าความซับซ้อนของเวลาน้อยลงเมื่อทำงานในคอมพิวเตอร์เชิงควอนตัม [en] กระบวนการของการค้นหาแบบทวิภาคควอนตัมที่แท้จริง หรือคือกระบวนการที่จะคืนค่าผลลัพธ์ที่ถูกต้องเสมอ จะต้องมีการตรวจสอบอย่างน้อย ${\textstyle {\frac {1}{\pi }}(\ln n-1)\approx 0.22\log _{2}n}$ ครั้งในกรณีที่แย่ที่สุด เมื่อ ${\textstyle \ln }$ คือ ลอการิทึมธรรมชาติ^[54] กระบวนการของการค้นหาแบบทวิภาคควอนตัมที่แท้จริงบางอันดำเนินการตรวจสอบทั้งหมด ${\textstyle 4\log _{605}n\approx 0.433\log _{2}n}$ ครั้งในกรณีที่แย่ที่สุด^[55] ในทางตรงกันข้าม ขั้นตอนวิธีของโกรเวอร์ [en] คือขั้นตอนวิธีควอนตัมที่ดีที่สุดสำหรับการค้นหาสมาชิกในรายการแบบไม่มีลำดับ โดยใช้การตรวจสอบทั้งหมด $O({\sqrt {n}})$ ครั้ง^[56]

ประวัติ[แก้]

แนวคิดเรื่องการเรียงลำดับข้อมูลในรายการเพื่อการค้นหาที่รวดเร็วขึ้นถูกคิดค้นตั้งแต่ในยุคโบราณ ตัวอย่างที่เก่าแก่ที่สุดที่เป็นที่รู้จักกันคือ แผ่นจารึก Inakibit-Anu ในอาณาจักรบาบิโลนในช่วง 200 ปีก่อนคริสตศักราช แผ่นจารึกประกอบด้วยตัวเลขฐานสิบหก [en] 500 ตัวและส่วนกลับของมันซึ่งถูกเรียงลำดับตามลำดับอักษร [en] ทำให้การค้นหาข้อมูลเฉพาะทำได้ง่ายขึ้น นอกจากนั้น รายการชื่อหลายรายการที่ถูกเรียงลำดับตามตัวอักษรตัวแรกของชื่อถูกค้นพบที่หมู่เกาะอีเจียน คาทอลิก ซึ่งคือพจนานุกรมภาษาละตินที่เขียนเสร็จในปีค.ศ. 1286 คือผลงานชิ้นแรกที่มีการอธิบายกฎการเรียงลำดับคำศัพท์ตามลำดับตัวอักษร ตรงข้ามกับการเรียงเพียงสองสามตัวอักษรแรก^[9]

ในปีค.ศ. 1946 จอห์น มอชลีย์ [en] ได้กล่าวถึงการค้นหาแบบทวิภาคเป็นครั้งแรกใน Moore School Lectures [en] ซึ่งคือหลักสูตรมหาวิทยาลัยพื้นฐานในด้านการคำนวณ^[9] ในปีค.ศ. 1957 วิลเลียม เวสลีย์ ปีเตอร์สัน [en] ได้ตีพิมพ์วิธีการแรกสำหรับการค้นหาโดยการประมาณช่วง^[9]^[57] ขั้นตอนวิธีการค้นหาแบบทวิภาคที่ถูกตีพิมพ์ทุกอันล้วนแต่ทำงานได้ในแถวลำดับที่มีขนาดน้อยกว่ากำลังของสองเท่ากับหนึ่ง ^[i] จนกระทั่งในปีค.ศ. 1960 เมื่อ Derrick Henry Lehmer [en] ได้ตีพิมพ์ขั้นตอนวิธีการค้นหาแบบทวิภาคที่สามารถทำงานได้ในแถวลำดับทุกประเภท^[59] ในปีค.ศ. 1962 Hermann Bottenbruch ได้นำเสนอการนำ ALGOL 60 [en] ไปใช้ในการค้นหาแบบทวิภาคที่วางการเปรียบเทียบความเท่ากันในกระบวนการท้ายสุด ซึ่งจะเพิ่มจำนวนการวนซ้ำโดยเฉลี่ยไปเท่ากับหนึ่ง แต่ลดจำนวนการเปรียบเทียบในหนึ่งการวนซ้ำเหลือเพียงหนึ่งครั้งเท่านั้น^[8] การค้นหาแบบทวิภาคอย่างมีเอกรูปถูกพัฒนาโดย A. K. Chandra จากมหาวิทยาลัยสแตนฟอร์ดในปีค.ศ. 1971^[9] ในปีค.ศ. 1986 เบอร์นาร์ด ชาเซลล์ [en] และ Leonidas J. Guibas [en] ได้คิดค้นการเรียงซ้อนแบบเศษส่วน [en] เพื่อแก้ปัญหาการค้นหาเกี่ยวกับเรขาคณิตเชิงคำนวณ [en]^[46]^[60]^[61]

ปัญหาการนำไปใช้งาน[แก้]

ถึงแม้แนวคิดพื้นฐานของการค้นหาแบบทวิภาคจะค่อนข้างตรงไปตรงมา แต่เนื้อหาของมันอาจซับซ้อนอย่างน่าประหลาดใจ
— โดนัลด์ คนูธ^[2]

เมื่อจอน เบนท์ลีย์ [en] ได้มอบหมายการค้นหาแบบทวิภาคให้เป็นงานในชั้นเรียนสำหรับโปรแกรมเมอร์มืออาชีพ เขาค้นพบว่าหลังการทำงานหลายชั่วโมง กว่า 90% ของโปรแกรมเมอร์ไม่สามารถหาคำตอบที่ถูกต้องได้ หลัก ๆ แล้วเป็นเพราะว่าโปรแกรมไม่สามารถทำงานได้ หรือไม่ก็คืนค่าที่ไม่ถูกต้องในการทดสอบกรณีขอบสุด [en] ^[62] การศึกษาที่ถูกตีพิมพ์ในปีค.ศ. 1988 พบว่าจากตำราเรียน 20 เล่ม มีเพียง 5 เล่มที่แสดงรหัส (code) ที่ถูกต้องสำหรับการค้นหาแบบทวิภาค^[63] ยิ่งไปกว่านั้น การใช้งานการค้นหาแบบทวิภาคของเบนท์ลีย์ซึ่งถูกตีพิมพ์ในหนังสือชื่อ Programming Pearls ในปีค.ศ. 1986 กลับมี overflow error [en] ที่ไม่ถูกตรวจพบกว่า 20 ปี คลังโปรแกรมภาษาจาวาสำหรับการค้นหาแบบทวิภาคก็มี overflow bug แบบเดียวกันมานานมากกว่า 9 ปี^[64]

ในการใช้งานจริง ตัวแปรที่แทนค่าดัชนีมักจะมีขนาดคงที่ (จำนวนเต็ม) ซึ่งอาจทำให้เกิดปัญหาค่าเกินขอบเขตตัวแปร [en] ในแถวลำดับที่มีขนาดใหญ่ได้ ถ้าค่ากลางมีค่าเท่ากับ ${\frac {L+R}{2}}$ แล้ว $L+R$ อาจมีค่าเกินขอบเขตของจำนวนเต็มของชนิดข้อมูลที่ใช้เก็บค่ากลางได้ ถึงแม้ $L$ และ $R$ จะมีค่าอยู่ภายในขอบเขตก็ตาม ถ้า $L$ และ $R$ ไม่เป็นลบ เราอาจหลีกเลี่ยงปัญหานี้ด้วยการคำนวณค่ากลางด้วยสมการ $L+{\frac {R-L}{2}}$ แทน^[65]

การวนอย่างไม่มีที่สิ้นสุดอาจเกิดขึ้นเมื่อเงื่อนไขการสิ้นสุดการวนนั้นไม่ชัดเจน เมื่อ $L$ มีค่าเกิน $R$ การค้นหาจะล้มเหลวและแสดงผลว่าการค้นหาล้มเหลว นอกจากนั้นแล้ว การวนจะต้องสิ้นสุดเมื่อค่าเป้าหมายถูกค้นพบแล้ว หรือเมื่อการค้นหาดำเนินการไปจนสุดแล้ว ดังนั้นการตรวจสอบว่าการค้นหานั้นสำเร็จหรือล้มเหลวจึงจำเป็นต้องทำในขั้นตอนท้ายสุดของการค้นหา เบนท์ลีย์ค้นพบว่าโปรแกรมเมอร์ส่วนใหญ่ที่ไม่สามารถใช้งานการค้นหาแบบทวิภาคได้มักจะสร้างข้อผิดพลาดเกี่ยวกับการกำหนดเงื่อนไขการสิ้นสุดการวน^[8]^[66]

คลังโปรแกรม[แก้]

คลังโปรแกรมที่รองรับและพร้อมใช้ในภาษาคอมพิวเตอร์ต่างๆ มีดังต่อไปนี้

ภาษาซีมีฟังก์ชัน bsearch()ในคลังโปรแกรมมาตรฐาน [en] ซึ่งโดยทั่วไปแล้วจะใช้งานผ่านการค้นหาแบบทวิภาค ถึงแม้จะไม่จำเป็นต้องใช้อย่างนั้นก็ตาม^[67]
ไลบรารีแม่แบบมาตรฐานของภาษาซีพลัสพลัสมีฟังก์ชัน binary_search(), lower_bound(), upper_bound() และ equal_range()^[68]
ในคลังโปรแกรมโฟบอส (Phobos) ของภาษาดี [en] โมดูล std.range มีชนิดข้อมูล SortedRange (คืนค่ามาจากฟังก์ชัน sort() และ assumeSorted()) และวิธีการ contains(), equaleRange(), lowerBound() และ trisect() ซึ่งใช้เทคนิคการค้นหาแบบทวิภาคเป็นค่าเริ่มต้นสำหรับขอบเขตที่มีการเข้าถึงแบบสุ่ม^[69]
ภาษาโคบอลมี SEARCH ALL สำหรับการดำเนินการค้นหาแบบทวิภาคในตารางโคบอลแบบมีลำดับ^[70]
ในแพ็กเกจคลังโปรแกรมมาตรฐาน sort ของภาษาโก [en] มีฟังก์ชัน Search, SearchInts, SearchFloat64s และ SearchStrings ซึ่งนำไปใช้ในการค้นหาแบบทวิภาคโดยทั่วไป รวมไปถึงการนำไปใช้งานโดยเฉพาะเพื่อค้นหาจำนวนเต็ม เลขทศนิยม และสตริง ตามลำดับ^[71]
ภาษาจาวามี binarySearch() ซึ่งเป็นชุดวิธีการแบบคงที่ที่โอเวอร์โหลด [en] ใน Arrays และ Collections ที่อยู่ในแพ็กเกจมาตรฐาน java.util สำหรับการดำเนินการค้นหาแบบทวิภาคบนแถวลำดับจาวาและบนรายการ ตามลำดับ^[72]^[73]
ดอตเน็ตเฟรมเวิร์ก 2.0 ของไมโครซอฟท์ มีขั้นตอนวิธีการค้นหาแบบทวิภาครุ่น generic [en] แบบคงที่ในกลุ่มคอลเล็กชันแบบฐาน ตัวอย่างเช่น วิธีการของ System.Array คือ BinarySearch<T>(T[] array, T value) ^[74]
สำหรับภาษาอ็อบเจกทีฟ-ซี กรอบงาน โกโก้ มีวิธีการ NSArray -indexOfObject:inSortedRange:options:usingComparator: ในแมคโอเอสเท็น 10.6+ ^[75] กรอบงาน Coure Foundation [en] ของแอปเปิลยังมีฟังก์ชัน CFArrayBSearchValues() ^[76]
ภาษาไพทอนมีโมดูล bisect ^[77]
คลาสแถวลำดับของภาษารูบีมีวิธีการ bsearch ซึ่งมีการหาคู่ที่ใกล้เคียงอยู่ในตัว^[78]

ดูเพิ่ม[แก้]

วิธีแบ่งครึ่ง

เชิงอรรถและอ้างอิง[แก้]

เชิงอรรถ[แก้]

↑ $O$ คือ สัญกรณ์โอใหญ่ และ $\log$ คือ ลอการิทึม ในสัญกรณ์โอใหญ่ ฐานของลอการิทึมไม่ใช่สิ่งที่สำคัญเนื่องจากลอการิทึมในรูปฐานหนึ่งก็สามารถเขียนในรูปลอการิทึมฐานอื่น ๆ ได้ นั่นคือ $\log _{b}(n)=\log _{k}(n)\div \log _{k}(b)$ เมื่อ $\log _{k}(b)$ เป็นค่าคงที่
↑ ขั้นตอนวิธีการค้นหาใด ๆ ที่อาศัยการเปรียบเทียบอย่างเดียวสามารถแสดงในรูปต้นไม้ค้นหาแบบทวิภาคได้ เส้นทางภายใน คือเส้นทางใด ๆ ที่เริ่มจากรากไปยังปมที่มีอยู่ในต้นไม้ ให้ $I$ เป็นความยาวของเส้นทางภายใน ซึ่งคือผลรวมความยาวของเส้นทางภายในทุกเส้นในต้นไม้ ถ้าสมาชิกแต่ละตัวมีโอกาสที่จะถูกค้นหาเท่ากัน กรณีเฉลี่ยจะเท่ากับ $1+{\frac {I}{n}}$ หรือก็คือหนึ่งบวกค่าเฉลี่ยของความยาวของเส้นทางภายในทั้งหมดในต้นไม้ เพราะเส้นทางภายในคือตัวแทนของสมาชิกที่ขั้นตอนวิธีการค้นหานั้นได้ดำเนินการเปรียบเทียบค่าของมันกับค่าเป้าหมาย ความยาวของเส้นทางภายในเหล่านี้แทนจำนวนการวนซ้ำหลังจากปมราก การเพิ่มค่าเฉลี่ยของความยาวนี้ในจำนวนการวนซ้ำหนึ่งครั้งที่รากจึงให้ผลลัพธ์เป็นกรณีเฉลี่ย ดังนั้น หากต้องการลดจำนวนการเปรียบเทียบโดยเฉลี่ยจะต้องลดค่าความยาวเส้นทางภายใน $I$ ซึ่งต้นไม้สำหรับการค้นหาแบบทวิภาคคือแบบต้นไม้ที่ได้ทำการลดความยาวเส้นทางภายในนี้แล้ว โดย Knuth 1998 ได้พิสูจน์ว่าความยาวเส้นทางภายนอก (ความยาวเส้นทางไปยังปมทุกปมที่มีปมลูกทั้งสองอยู่แล้ว) จะลดลงเมื่อปมภายนอก (ปมที่ไม่มีปมลูก) อยู่ระหว่างชั้นสองชั้นที่ติดกันของต้นไม้ สิ่งนี้ยังสามารถนำไปประยุกต์ใช้กับเส้นทางภายในได้อีกด้วย เนื่องจากความยาวเส้นทางภายใน $I$ มีความสัมพันธ์เชิงเส้นตรงกับความยาวเส้นทางภายนอก $E$ สำหรับต้นไม้ที่มีปม $n$ ปม จะได้ว่า $I=E-2n$ เมื่อต้นไม้ย่อยแต่ละต้นมีจำนวนปมที่เท่ากัน หรือคือแถวลำดับนั้นสามารถถูกแบ่งครึ่งได้ขนาดเท่ากันในทุกการวนซ้ำ แล้วปมภายนอกและปมพ่อแม่ภายในของมันจะอยู่ภายในสองชั้นที่ติดกันนั้น จึงกล่าวได้ว่า การค้นหาแบบทวิภาคสามารถลดจำนวนการเปรียบเทียบโดยเฉลี่ยได้เนื่องจากต้นไม้เปรียบเทียบของมันมีความยาวเส้นทางภายในที่น้อยที่สุดเท่าที่จะเป็นไปได้^[14]
↑ Knuth 1998 ได้แสดงบนแบบจำลองคอมพิวเตอร์ MIX [en] ของเขา (ซึ่งถูกออกแบบเพื่อเป็นตัวแทนของคอมพิวเตอร์ธรรมดา) ว่าเวลาการดำเนินการโดยเฉลี่ยสำหรับการค้นหาที่สำเร็จคือ ${\textstyle 17.5\log _{2}n+17}$ เปรียบเทียบกับ ${\textstyle 18\log _{2}n-16}$ สำหรับการค้นหาแบบทวิภาคปกติ ความซับซ้อนของเวลาในกรณีนี้จะเพิ่มขึ้นช้ากว่าเล็กน้อย แต่จะมีค่าเริ่มต้นที่มากกว่า^[18]
↑ Knuth 1998 ได้ทำการวิเคราะห์ประสิทธิภาพด้านเวลาอย่างเป็นทางการของขั้นตอนวิธีการค้นหาทั้งสองนี้ ในคอมพิวเตอร์ MIX [en] ของเขา ซึ่งเขาได้ออกแบบเพื่อเป็นตัวแทนของคอมพิวเตอร์ทั่วไป การค้นหาแบบทวิภาคใช้เวลา ${\textstyle 18\log n-16}$ โดยเฉลี่ยสำหรับการค้นหาที่สำเร็จ ในขณะที่การค้นหาเชิงเส้นที่มี sentinell node [en] ที่ท้ายรายการจะใช้เวลา ${\textstyle 1.75n+8.5-{\frac {n{\text{ mod }}2}{4n}}}$ การค้นหาเชิงเส้นจะมีค่าความซับซ้อนเริ่มต้นน้อยกว่า เพราะต้องใช้การคำนวณน้อยกว่า แต่ค่าความซับซ้อนจะมีค่าเพิ่มขึ้นรวดเร็วกว่าการค้นหาแบบทวิภาค ในคอมพิวเตอร์ MIX การค้นหาแบบทวิภาคจะทำงานได้ดีกว่าการค้นหาเชิงเส้นที่มี sentinel node เมื่อ ${\textstyle n>44}$ ^[14]^[23]
↑ การเพิ่มค่าในลำดับที่มีการเรียงแล้วหรือในรูปแบบคีย์สลับสูงสุดและต่ำสุดจะให้ผลลัพธ์เป็นต้นไม้ค้นหาแบบทวิภาคที่มีเวลาการดำเนินการที่มากที่สุดในกรณีเฉลี่ยและกรณีที่แย่ที่สุด^[28]
↑ การค้นหาในตารางแฮชบางอันสามารถดำเนินการด้วยเวลาที่แน่นอนได้^[33]
↑ เนื่องจากการตั้งค่าบิตทั้งหมดที่ฟังก์ชันแฮชชี้ไปสำหรับคีย์เฉพาะอาจส่งผลกระทบต่อการตรวจสอบคีย์อื่น ๆ ที่มีตำแหน่งแฮชเดียวกันได้^[38]
↑ มีการปรับปรุงตัวกรองของบลูมเพื่อพัฒนาค่าความซับซ้อนหรือเพื่อสนับสนุนการดำเนินการลบสมาชิก ตัวอย่างเช่น ตัวกรองนกกาเหว่าซึ่งใช้ cuckoo hashing [en] เพื่อพัฒนาประสิทธิภาพ^[38]
↑ นั่นคือ แถวลำดับที่มีขนาดเท่ากับ 1, 3, 7, 15, 31 ...^[58]

อ้างอิง[แก้]

↑ Williams, Jr., Louis F. (22 เมษายน 1976). A modification to the half-interval search (binary search) method. Proceedings of the 14th ACM Southeast Conference. ACM. pp. 95–101. doi:10.1145/503561.503582. เก็บจากแหล่งเดิมเมื่อ 12 มีนาคม 2017. สืบค้นเมื่อ 29 มิถุนายน 2018.
↑ ^2.0 ^2.1 Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Binary search".
↑ Butterfield & Ngondi 2016, p. 46.
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
↑ เอริก ดับเบิลยู. ไวส์สไตน์, "Binary Search" จากแมทเวิลด์.
↑ ^6.0 ^6.1 Flores, Ivan; Madpis, George (1 September 1971). "Average binary search length for dense ordered lists". Communications of the ACM. 14 (9): 602–603. doi:10.1145/362663.362752. ISSN 0001-0782. S2CID 43325465.
↑ ^7.0 ^7.1 ^7.2 Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm B".
↑ ^8.0 ^8.1 ^8.2 ^8.3 Bottenbruch, Hermann (1 April 1962). "Structure and use of ALGOL 60". Journal of the ACM. 9 (2): 161–221. doi:10.1145/321119.321120. ISSN 0004-5411. S2CID 13406983. Procedure is described at p. 214 (§43), titled "Program for Binary Search".
↑ ^9.0 ^9.1 ^9.2 ^9.3 ^9.4 ^9.5 Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "History and bibliography".
↑ ^10.0 ^10.1 Kasahara & Morishita 2006, pp. 8–9.
↑ ^11.0 ^11.1 ^11.2 Sedgewick & Wayne 2011, §3.1, subsection "Rank and selection".
↑ ^12.0 ^12.1 Goldman & Goldman 2008, pp. 461–463.
↑ Sedgewick & Wayne 2011, §3.1, subsection "Range queries".
↑ ^14.00 ^14.01 ^14.02 ^14.03 ^14.04 ^14.05 ^14.06 ^14.07 ^14.08 ^14.09 ^14.10 ^14.11 Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search".
↑ Knuth 1998, §6.2.1 ("Searching an ordered table"), "Theorem B".
↑ Chang 2003, p. 169.
↑ ^17.0 ^17.1 ^17.2 Knuth 1997, §2.3.4.5 ("Path length").
↑ ^18.0 ^18.1 Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Exercise 23".
↑ Rolfe, Timothy J. (1997). "Analytic derivation of comparisons in binary search". ACM SIGNUM Newsletter. 32 (4): 15–19. doi:10.1145/289251.289255. S2CID 23752485.
↑ Khuong, Paul-Virak; Morin, Pat (2017). "Array Layouts for Comparison-Based Searching". Journal of Experimental Algorithmics. 22. Article 1.3. arXiv:1509.05053. doi:10.1145/3053370. S2CID 23752485.
↑ Knuth 1997, §2.2.2 ("Sequential Allocation").
↑ ^22.0 ^22.1 ^22.2 ^22.3 Beame, Paul; Fich, Faith E. (2001). "Optimal bounds for the predecessor problem and related problems". Journal of Computer and System Sciences. 65 (1): 38–72. doi:10.1006/jcss.2002.1822.
↑ Knuth 1998, Answers to Exercises (§6.2.1) for "Exercise 5".
↑ Knuth 1998, §6.2.1 ("Searching an ordered table").
↑ Knuth 1998, §5.3.1 ("Minimum-Comparison sorting").
↑ Sedgewick & Wayne 2011, §3.2 ("Ordered symbol tables").
↑ Sedgewick & Wayne 2011, §3.2 ("Binary Search Trees"), subsection "Order-based methods and deletion".
↑ Knuth 1998, §6.2.2 ("Binary tree searching"), subsection "But what about the worst case?".
↑ Sedgewick & Wayne 2011, §3.5 ("Applications"), "Which symbol-table implementation should I use?".
↑ Knuth 1998, §5.4.9 ("Disks and Drums").
↑ Knuth 1998, §6.2.4 ("Multiway trees").
↑ Knuth 1998, §6.4 ("Hashing").
↑ Knuth 1998, §6.4 ("Hashing"), subsection "History".
↑ Dietzfelbinger, Martin; Karlin, Anna; Mehlhorn, Kurt; Meyer auf der Heide, Friedhelm; Rohnert, Hans; Tarjan, Robert E. (August 1994). "Dynamic perfect hashing: upper and lower bounds". SIAM Journal on Computing. 23 (4): 738–761. doi:10.1137/S0097539791194094.
↑ Morin, Pat. "Hash tables" (PDF). p. 1. สืบค้นเมื่อ 28 March 2016.
↑ Knuth 2011, §7.1.3 ("Bitwise Tricks and Techniques").
↑ ^37.0 ^37.1 Silverstein, Alan, Judy IV shop manual (PDF), Hewlett-Packard, pp. 80–81
↑ ^38.0 ^38.1 Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014). Cuckoo filter: practically better than Bloom. Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies. pp. 75–88. doi:10.1145/2674005.2674994.
↑ Bloom, Burton H. (1970). "Space/time trade-offs in hash coding with allowable errors". Communications of the ACM. 13 (7): 422–426. CiteSeerX 10.1.1.641.9096. doi:10.1145/362686.362692. S2CID 7931252.
↑ Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "An important variation".
↑ Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm U".
↑ Moffat & Turpin 2002, p. 33.
↑ ^43.0 ^43.1 ^43.2 Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Interpolation search".
↑ Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Exercise 22".
↑ Perl, Yehoshua; Itai, Alon; Avni, Haim (1978). "Interpolation search—a log log n search". Communications of the ACM. 21 (7): 550–553. doi:10.1145/359545.359557. S2CID 11089655.
↑ ^46.0 ^46.1 ^46.2 Chazelle, Bernard; Liu, Ding (6 July 2001). Lower bounds for intersection searching and fractional cascading in higher dimension. 33rd ACM Symposium on Theory of Computing. ACM. pp. 322–329. doi:10.1145/380752.380818. ISBN 978-1-58113-349-3. สืบค้นเมื่อ 30 June 2018.
↑ Chazelle, Bernard; Liu, Ding (1 March 2004). "Lower bounds for intersection searching and fractional cascading in higher dimension" (PDF). Journal of Computer and System Sciences (ภาษาอังกฤษ). 68 (2): 269–284. CiteSeerX 10.1.1.298.7772. doi:10.1016/j.jcss.2003.07.003. ISSN 0022-0000. สืบค้นเมื่อ 30 June 2018.
↑ Emamjomeh-Zadeh, Ehsan; Kempe, David; Singhal, Vikrant (2016). Deterministic and probabilistic binary search in graphs. 48th ACM Symposium on Theory of Computing. pp. 519–532. arXiv:1503.00805. doi:10.1145/2897518.2897656.
↑ Ben-Or, Michael; Hassidim, Avinatan (2008). "The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)" (PDF). 49th Symposium on Foundations of Computer Science. pp. 221–230. doi:10.1109/FOCS.2008.58. ISBN 978-0-7695-3436-7.
↑ Pelc, Andrzej (1989). "Searching with known error probability". Theoretical Computer Science. 63 (2): 185–202. doi:10.1016/0304-3975(89)90077-7.
↑ Rivest, Ronald L.; Meyer, Albert R.; Kleitman, Daniel J.; Winklmann, K. Coping with errors in binary search procedures. 10th ACM Symposium on Theory of Computing. doi:10.1145/800133.804351.
↑ Pelc, Andrzej (2002). "Searching games with errors—fifty years of coping with liars". Theoretical Computer Science. 270 (1–2): 71–109. doi:10.1016/S0304-3975(01)00303-6.
↑ Rényi, Alfréd (1961). "On a problem in information theory". Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei (ภาษาฮังการี). 6: 505–516. MR 0143666.
↑ Høyer, Peter; Neerbek, Jan; Shi, Yaoyun (2002). "Quantum complexities of ordered searching, sorting, and element distinctness". Algorithmica. 34 (4): 429–448. arXiv:quant-ph/0102078. doi:10.1007/s00453-002-0976-3. S2CID 13717616.
↑ Childs, Andrew M.; Landahl, Andrew J.; Parrilo, Pablo A. (2007). "Quantum algorithms for the ordered search problem via semidefinite programming". Physical Review A. 75 (3). 032335. arXiv:quant-ph/0608161. Bibcode:2007PhRvA..75c2335C. doi:10.1103/PhysRevA.75.032335. S2CID 41539957.
↑ Grover, Lov K. (1996). A fast quantum mechanical algorithm for database search. 28th ACM Symposium on Theory of Computing. Philadelphia, PA. pp. 212–219. arXiv:quant-ph/9605043. doi:10.1145/237814.237866.
↑ Peterson, William Wesley (1957). "Addressing for random-access storage". IBM Journal of Research and Development. 1 (2): 130–146. doi:10.1147/rd.12.0130.
↑ "2ⁿ−1". OEIS A000225 เก็บถาวร 8 มิถุนายน 2016 ที่ เวย์แบ็กแมชชีน. Retrieved 7 May 2016.
↑ Lehmer, Derrick (1960). Teaching combinatorial tricks to a computer. Proceedings of Symposia in Applied Mathematics. Vol. 10. pp. 180–181. doi:10.1090/psapm/010.
↑ Chazelle, Bernard; Guibas, Leonidas J. (1986). "Fractional cascading: I. A data structuring technique" (PDF). Algorithmica. 1 (1–4): 133–162. CiteSeerX 10.1.1.117.8349. doi:10.1007/BF01840440. S2CID 12745042.
↑ Chazelle, Bernard; Guibas, Leonidas J. (1986), "Fractional cascading: II. Applications" (PDF), Algorithmica, 1 (1–4): 163–191, doi:10.1007/BF01840441, S2CID 11232235
↑ Bentley 2000, §4.1 ("The Challenge of Binary Search").
↑ Pattis, Richard E. (1988). "Textbook errors in binary searching". SIGCSE Bulletin. 20: 190–194. doi:10.1145/52965.53012.
↑ Bloch, Joshua (2 มิถุนายน 2006). "Extra, extra – read all about it: nearly all binary searches and mergesorts are broken". Google Research Blog. เก็บจากแหล่งเดิมเมื่อ 1 เมษายน 2016. สืบค้นเมื่อ 21 เมษายน 2016.
↑ Ruggieri, Salvatore (2003). "On computing the semi-sum of two integers" (PDF). Information Processing Letters. 87 (2): 67–71. CiteSeerX 10.1.1.13.5631. doi:10.1016/S0020-0190(03)00263-1. เก็บ (PDF)จากแหล่งเดิมเมื่อ 3 กรกฎาคม 2006. สืบค้นเมื่อ 19 มีนาคม 2016.
↑ Bentley 2000, §4.4 ("Principles").
↑ "bsearch – binary search a sorted table". The Open Group Base Specifications (7th ed.). The Open Group. 2013. เก็บจากแหล่งเดิมเมื่อ 21 มีนาคม 2016. สืบค้นเมื่อ 28 มีนาคม 2016.
↑ Stroustrup 2013, p. 945.
↑ "std.range - D Programming Language". dlang.org. สืบค้นเมื่อ 2020-04-29.
↑ Unisys (2012), COBOL ANSI-85 programming reference manual, vol. 1, pp. 598–601
↑ "Package sort". The Go Programming Language. เก็บจากแหล่งเดิมเมื่อ 25 เมษายน 2016. สืบค้นเมื่อ 28 เมษายน 2016.
↑ "java.util.Arrays". Java Platform Standard Edition 8 Documentation. Oracle Corporation. เก็บจากแหล่งเดิมเมื่อ 29 เมษายน 2016. สืบค้นเมื่อ 1 พฤษภาคม 2016.
↑ "java.util.Collections". Java Platform Standard Edition 8 Documentation. Oracle Corporation. เก็บจากแหล่งเดิมเมื่อ 23 เมษายน 2016. สืบค้นเมื่อ 1 พฤษภาคม 2016.
↑ "List<T>.BinarySearch method (T)". Microsoft Developer Network. เก็บจากแหล่งเดิมเมื่อ 7 พฤษภาคม 2016. สืบค้นเมื่อ 10 เมษายน 2016.
↑ "NSArray". Mac Developer Library. Apple Inc. เก็บจากแหล่งเดิมเมื่อ 17 เมษายน 2016. สืบค้นเมื่อ 1 พฤษภาคม 2016.
↑ "CFArray". Mac Developer Library. Apple Inc. เก็บจากแหล่งเดิมเมื่อ 20 เมษายน 2016. สืบค้นเมื่อ 1 พฤษภาคม 2016.
↑ "8.6. bisect — Array bisection algorithm". The Python Standard Library. Python Software Foundation. เก็บจากแหล่งเดิมเมื่อ 25 มีนาคม 2018. สืบค้นเมื่อ 26 มีนาคม 2018.
↑ Fitzgerald 2015, p. 152.

บรรณานุกรม[แก้]

Bentley, Jon (2000). Programming pearls (2nd ed.). Addison-Wesley. ISBN 978-0-201-65788-3.
Butterfield, Andrew; Ngondi, Gerard E. (2016). A dictionary of computer science (7th ed.). Oxford, UK: Oxford University Press. ISBN 978-0-19-968897-5.
Chang, Shi-Kuo (2003). Data structures and algorithms. Software Engineering and Knowledge Engineering. Vol. 13. Singapore: World Scientific. ISBN 978-981-238-348-8.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 978-0-262-03384-8.
Fitzgerald, Michael (2015). Ruby pocket reference. Sebastopol, California: O'Reilly Media. ISBN 978-1-4919-2601-7.
Goldman, Sally A.; Goldman, Kenneth J. (2008). A practical guide to data structures and algorithms using Java. Boca Raton, Florida: CRC Press. ISBN 978-1-58488-455-2.
Kasahara, Masahiro; Morishita, Shinichi (2006). Large-scale genome sequence processing. London, UK: Imperial College Press. ISBN 978-1-86094-635-6.
Knuth, Donald (1997). Fundamental algorithms. The Art of Computer Programming. Vol. 1 (3rd ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-89683-1.
Knuth, Donald (1998). Sorting and searching. The Art of Computer Programming. Vol. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-89685-5.
Knuth, Donald (2011). Combinatorial algorithms. The Art of Computer Programming. Vol. 4A (1st ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-03804-0.
Moffat, Alistair; Turpin, Andrew (2002). Compression and coding algorithms. Hamburg, Germany: Kluwer Academic Publishers. doi:10.1007/978-1-4615-0935-6. ISBN 978-0-7923-7668-2.
Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (4th ed.). Upper Saddle River, New Jersey: Addison-Wesley Professional. ISBN 978-0-321-57351-3. Condensed web version ; book version .
Stroustrup, Bjarne (2013). The C++ programming language (4th ed.). Upper Saddle River, New Jersey: Addison-Wesley Professional. ISBN 978-0-321-56384-2.

แหล่งข้อมูลอื่น[แก้]

[6] $O$ คือ สัญกรณ์โอใหญ่ และ $\log$ คือ ลอการิทึม ในสัญกรณ์โอใหญ่ ฐานของลอการิทึมไม่ใช่สิ่งที่สำคัญเนื่องจากลอการิทึมในรูปฐานหนึ่งก็สามารถเขียนในรูปลอการิทึมฐานอื่น ๆ ได้ นั่นคือ $\log _{b}(n)=\log _{k}(n)\div \log _{k}(b)$ เมื่อ $\log _{k}(b)$ เป็นค่าคงที่

[18] ขั้นตอนวิธีการค้นหาใด ๆ ที่อาศัยการเปรียบเทียบอย่างเดียวสามารถแสดงในรูปต้นไม้ค้นหาแบบทวิภาคได้ เส้นทางภายใน คือเส้นทางใด ๆ ที่เริ่มจากรากไปยังปมที่มีอยู่ในต้นไม้ ให้ $I$ เป็นความยาวของเส้นทางภายใน ซึ่งคือผลรวมความยาวของเส้นทางภายในทุกเส้นในต้นไม้ ถ้าสมาชิกแต่ละตัวมีโอกาสที่จะถูกค้นหาเท่ากัน กรณีเฉลี่ยจะเท่ากับ $1+{\frac {I}{n}}$ หรือก็คือหนึ่งบวกค่าเฉลี่ยของความยาวของเส้นทางภายในทั้งหมดในต้นไม้ เพราะเส้นทางภายในคือตัวแทนของสมาชิกที่ขั้นตอนวิธีการค้นหานั้นได้ดำเนินการเปรียบเทียบค่าของมันกับค่าเป้าหมาย ความยาวของเส้นทางภายในเหล่านี้แทนจำนวนการวนซ้ำหลังจากปมราก การเพิ่มค่าเฉลี่ยของความยาวนี้ในจำนวนการวนซ้ำหนึ่งครั้งที่รากจึงให้ผลลัพธ์เป็นกรณีเฉลี่ย ดังนั้น หากต้องการลดจำนวนการเปรียบเทียบโดยเฉลี่ยจะต้องลดค่าความยาวเส้นทางภายใน $I$ ซึ่งต้นไม้สำหรับการค้นหาแบบทวิภาคคือแบบต้นไม้ที่ได้ทำการลดความยาวเส้นทางภายในนี้แล้ว โดย Knuth 1998 ได้พิสูจน์ว่าความยาวเส้นทางภายนอก (ความยาวเส้นทางไปยังปมทุกปมที่มีปมลูกทั้งสองอยู่แล้ว) จะลดลงเมื่อปมภายนอก (ปมที่ไม่มีปมลูก) อยู่ระหว่างชั้นสองชั้นที่ติดกันของต้นไม้ สิ่งนี้ยังสามารถนำไปประยุกต์ใช้กับเส้นทางภายในได้อีกด้วย เนื่องจากความยาวเส้นทางภายใน $I$ มีความสัมพันธ์เชิงเส้นตรงกับความยาวเส้นทางภายนอก $E$ สำหรับต้นไม้ที่มีปม $n$ ปม จะได้ว่า $I=E-2n$ เมื่อต้นไม้ย่อยแต่ละต้นมีจำนวนปมที่เท่ากัน หรือคือแถวลำดับนั้นสามารถถูกแบ่งครึ่งได้ขนาดเท่ากันในทุกการวนซ้ำ แล้วปมภายนอกและปมพ่อแม่ภายในของมันจะอยู่ภายในสองชั้นที่ติดกันนั้น จึงกล่าวได้ว่า การค้นหาแบบทวิภาคสามารถลดจำนวนการเปรียบเทียบโดยเฉลี่ยได้เนื่องจากต้นไม้เปรียบเทียบของมันมีความยาวเส้นทางภายในที่น้อยที่สุดเท่าที่จะเป็นไปได้^[14]

[21] Knuth 1998 ได้แสดงบนแบบจำลองคอมพิวเตอร์ MIX [en] ของเขา (ซึ่งถูกออกแบบเพื่อเป็นตัวแทนของคอมพิวเตอร์ธรรมดา) ว่าเวลาการดำเนินการโดยเฉลี่ยสำหรับการค้นหาที่สำเร็จคือ ${\textstyle 17.5\log _{2}n+17}$ เปรียบเทียบกับ ${\textstyle 18\log _{2}n-16}$ สำหรับการค้นหาแบบทวิภาคปกติ ความซับซ้อนของเวลาในกรณีนี้จะเพิ่มขึ้นช้ากว่าเล็กน้อย แต่จะมีค่าเริ่มต้นที่มากกว่า^[18]

[27] Knuth 1998 ได้ทำการวิเคราะห์ประสิทธิภาพด้านเวลาอย่างเป็นทางการของขั้นตอนวิธีการค้นหาทั้งสองนี้ ในคอมพิวเตอร์ MIX [en] ของเขา ซึ่งเขาได้ออกแบบเพื่อเป็นตัวแทนของคอมพิวเตอร์ทั่วไป การค้นหาแบบทวิภาคใช้เวลา ${\textstyle 18\log n-16}$ โดยเฉลี่ยสำหรับการค้นหาที่สำเร็จ ในขณะที่การค้นหาเชิงเส้นที่มี sentinell node [en] ที่ท้ายรายการจะใช้เวลา ${\textstyle 1.75n+8.5-{\frac {n{\text{ mod }}2}{4n}}}$ การค้นหาเชิงเส้นจะมีค่าความซับซ้อนเริ่มต้นน้อยกว่า เพราะต้องใช้การคำนวณน้อยกว่า แต่ค่าความซับซ้อนจะมีค่าเพิ่มขึ้นรวดเร็วกว่าการค้นหาแบบทวิภาค ในคอมพิวเตอร์ MIX การค้นหาแบบทวิภาคจะทำงานได้ดีกว่าการค้นหาเชิงเส้นที่มี sentinel node เมื่อ ${\textstyle n>44}$ ^[14]^[23]

[33] การเพิ่มค่าในลำดับที่มีการเรียงแล้วหรือในรูปแบบคีย์สลับสูงสุดและต่ำสุดจะให้ผลลัพธ์เป็นต้นไม้ค้นหาแบบทวิภาคที่มีเวลาการดำเนินการที่มากที่สุดในกรณีเฉลี่ยและกรณีที่แย่ที่สุด^[28]

[39] การค้นหาในตารางแฮชบางอันสามารถดำเนินการด้วยเวลาที่แน่นอนได้^[33]

[45] เนื่องจากการตั้งค่าบิตทั้งหมดที่ฟังก์ชันแฮชชี้ไปสำหรับคีย์เฉพาะอาจส่งผลกระทบต่อการตรวจสอบคีย์อื่น ๆ ที่มีตำแหน่งแฮชเดียวกันได้^[38]

[46] มีการปรับปรุงตัวกรองของบลูมเพื่อพัฒนาค่าความซับซ้อนหรือเพื่อสนับสนุนการดำเนินการลบสมาชิก ตัวอย่างเช่น ตัวกรองนกกาเหว่าซึ่งใช้ cuckoo hashing [en] เพื่อพัฒนาประสิทธิภาพ^[38]

[67] นั่นคือ แถวลำดับที่มีขนาดเท่ากับ 1, 3, 7, 15, 31 ...^[58]

[Williams1976-1] Williams, Jr., Louis F. (22 เมษายน 1976). A modification to the half-interval search (binary search) method. Proceedings of the 14th ACM Southeast Conference. ACM. pp. 95–101. doi:10.1145/503561.503582. เก็บจากแหล่งเดิมเมื่อ 12 มีนาคม 2017. สืบค้นเมื่อ 29 มิถุนายน 2018.

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Binary_search"-2] 2.0 ^2.1 Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Binary search".

[FOOTNOTEButterfieldNgondi201646-3] Butterfield & Ngondi 2016, p. 46.

[4] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.

[5] เอริก ดับเบิลยู. ไวส์สไตน์, "Binary Search" จากแมทเวิลด์.

[FloresMadpis1971-7] 6.0 ^6.1 Flores, Ivan; Madpis, George (1 September 1971). "Average binary search length for dense ordered lists". Communications of the ACM. 14 (9): 602–603. doi:10.1145/362663.362752. ISSN 0001-0782. S2CID 43325465.

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Algorithm_B"-8] 7.0 ^7.1 ^7.2 Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm B".

[Bottenbruch1962-9] 8.0 ^8.1 ^8.2 ^8.3 Bottenbruch, Hermann (1 April 1962). "Structure and use of ALGOL 60". Journal of the ACM. 9 (2): 161–221. doi:10.1145/321119.321120. ISSN 0004-5411. S2CID 13406983. Procedure is described at p. 214 (§43), titled "Program for Binary Search".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"History_and_bibliography"-10] 9.0 ^9.1 ^9.2 ^9.3 ^9.4 ^9.5 Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "History and bibliography".

[FOOTNOTEKasaharaMorishita20068–9-11] 10.0 ^10.1 Kasahara & Morishita 2006, pp. 8–9.

[FOOTNOTESedgewickWayne2011§3.1,_subsection_"Rank_and_selection"-12] 11.0 ^11.1 ^11.2 Sedgewick & Wayne 2011, §3.1, subsection "Rank and selection".

[FOOTNOTEGoldmanGoldman2008461–463-13] 12.0 ^12.1 Goldman & Goldman 2008, pp. 461–463.

[FOOTNOTESedgewickWayne2011§3.1,_subsection_"Range_queries"-14] Sedgewick & Wayne 2011, §3.1, subsection "Range queries".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Further_analysis_of_binary_search"-15] 14.00 ^14.01 ^14.02 ^14.03 ^14.04 ^14.05 ^14.06 ^14.07 ^14.08 ^14.09 ^14.10 ^14.11 Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_"Theorem_B"-16] Knuth 1998, §6.2.1 ("Searching an ordered table"), "Theorem B".

[FOOTNOTEChang2003169-17] Chang 2003, p. 169.

[FOOTNOTEKnuth1997§2.3.4.5_("Path_length")-19] 17.0 ^17.1 ^17.2 Knuth 1997, §2.3.4.5 ("Path length").

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Exercise_23"-20] 18.0 ^18.1 Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Exercise 23".

[22] Rolfe, Timothy J. (1997). "Analytic derivation of comparisons in binary search". ACM SIGNUM Newsletter. 32 (4): 15–19. doi:10.1145/289251.289255. S2CID 23752485.

[23] Khuong, Paul-Virak; Morin, Pat (2017). "Array Layouts for Comparison-Based Searching". Journal of Experimental Algorithmics. 22. Article 1.3. arXiv:1509.05053. doi:10.1145/3053370. S2CID 23752485.

[FOOTNOTEKnuth1997§2.2.2_("Sequential_Allocation")-24] Knuth 1997, §2.2.2 ("Sequential Allocation").

[pred-25] 22.0 ^22.1 ^22.2 ^22.3 Beame, Paul; Fich, Faith E. (2001). "Optimal bounds for the predecessor problem and related problems". Journal of Computer and System Sciences. 65 (1): 38–72. doi:10.1006/jcss.2002.1822.

[FOOTNOTEKnuth1998Answers_to_Exercises_(§6.2.1)_for_"Exercise_5"-26] Knuth 1998, Answers to Exercises (§6.2.1) for "Exercise 5".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table")-28] Knuth 1998, §6.2.1 ("Searching an ordered table").

[FOOTNOTEKnuth1998§5.3.1_("Minimum-Comparison_sorting")-29] Knuth 1998, §5.3.1 ("Minimum-Comparison sorting").

[FOOTNOTESedgewickWayne2011§3.2_("Ordered_symbol_tables")-30] Sedgewick & Wayne 2011, §3.2 ("Ordered symbol tables").

[FOOTNOTESedgewickWayne2011§3.2_("Binary_Search_Trees"),_subsection_"Order-based_methods_and_deletion"-31] Sedgewick & Wayne 2011, §3.2 ("Binary Search Trees"), subsection "Order-based methods and deletion".

[FOOTNOTEKnuth1998§6.2.2_("Binary_tree_searching"),_subsection_"But_what_about_the_worst_case?"-32] Knuth 1998, §6.2.2 ("Binary tree searching"), subsection "But what about the worst case?".

[FOOTNOTESedgewickWayne2011§3.5_("Applications"),_"Which_symbol-table_implementation_should_I_use?"-34] Sedgewick & Wayne 2011, §3.5 ("Applications"), "Which symbol-table implementation should I use?".

[FOOTNOTEKnuth1998§5.4.9_("Disks_and_Drums")-35] Knuth 1998, §5.4.9 ("Disks and Drums").

[FOOTNOTEKnuth1998§6.2.4_("Multiway_trees")-36] Knuth 1998, §6.2.4 ("Multiway trees").

[FOOTNOTEKnuth1998§6.4_("Hashing")-37] Knuth 1998, §6.4 ("Hashing").

[FOOTNOTEKnuth1998§6.4_("Hashing"),_subsection_"History"-38] Knuth 1998, §6.4 ("Hashing"), subsection "History".

[40] Dietzfelbinger, Martin; Karlin, Anna; Mehlhorn, Kurt; Meyer auf der Heide, Friedhelm; Rohnert, Hans; Tarjan, Robert E. (August 1994). "Dynamic perfect hashing: upper and lower bounds". SIAM Journal on Computing. 23 (4): 738–761. doi:10.1137/S0097539791194094.

[41] Morin, Pat. "Hash tables" (PDF). p. 1. สืบค้นเมื่อ 28 March 2016.

[FOOTNOTEKnuth2011§7.1.3_("Bitwise_Tricks_and_Techniques")-42] Knuth 2011, §7.1.3 ("Bitwise Tricks and Techniques").

[judyarray-43] 37.0 ^37.1 Silverstein, Alan, Judy IV shop manual (PDF), Hewlett-Packard, pp. 80–81

[cuckoofilter-44] 38.0 ^38.1 Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014). Cuckoo filter: practically better than Bloom. Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies. pp. 75–88. doi:10.1145/2674005.2674994.

[47] Bloom, Burton H. (1970). "Space/time trade-offs in hash coding with allowable errors". Communications of the ACM. 13 (7): 422–426. CiteSeerX 10.1.1.641.9096. doi:10.1145/362686.362692. S2CID 7931252.

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"An_important_variation"-48] Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "An important variation".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Algorithm_U"-49] Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm U".

[FOOTNOTEMoffatTurpin200233-50] Moffat & Turpin 2002, p. 33.

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Interpolation_search"-51] 43.0 ^43.1 ^43.2 Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Interpolation search".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Exercise_22"-52] Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Exercise 22".

[53] Perl, Yehoshua; Itai, Alon; Avni, Haim (1978). "Interpolation search—a log log n search". Communications of the ACM. 21 (7): 550–553. doi:10.1145/359545.359557. S2CID 11089655.

[ChazelleLiu2001-54] 46.0 ^46.1 ^46.2 Chazelle, Bernard; Liu, Ding (6 July 2001). Lower bounds for intersection searching and fractional cascading in higher dimension. 33rd ACM Symposium on Theory of Computing. ACM. pp. 322–329. doi:10.1145/380752.380818. ISBN 978-1-58113-349-3. สืบค้นเมื่อ 30 June 2018.

[ChazelleLiu2004-55] Chazelle, Bernard; Liu, Ding (1 March 2004). "Lower bounds for intersection searching and fractional cascading in higher dimension" (PDF). Journal of Computer and System Sciences (ภาษาอังกฤษ). 68 (2): 269–284. CiteSeerX 10.1.1.298.7772. doi:10.1016/j.jcss.2003.07.003. ISSN 0022-0000. สืบค้นเมื่อ 30 June 2018.

[56] Emamjomeh-Zadeh, Ehsan; Kempe, David; Singhal, Vikrant (2016). Deterministic and probabilistic binary search in graphs. 48th ACM Symposium on Theory of Computing. pp. 519–532. arXiv:1503.00805. doi:10.1145/2897518.2897656.

[57] Ben-Or, Michael; Hassidim, Avinatan (2008). "The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)" (PDF). 49th Symposium on Foundations of Computer Science. pp. 221–230. doi:10.1109/FOCS.2008.58. ISBN 978-0-7695-3436-7.

[pelc1989-58] Pelc, Andrzej (1989). "Searching with known error probability". Theoretical Computer Science. 63 (2): 185–202. doi:10.1016/0304-3975(89)90077-7.

[59] Rivest, Ronald L.; Meyer, Albert R.; Kleitman, Daniel J.; Winklmann, K. Coping with errors in binary search procedures. 10th ACM Symposium on Theory of Computing. doi:10.1145/800133.804351.

[60] Pelc, Andrzej (2002). "Searching games with errors—fifty years of coping with liars". Theoretical Computer Science. 270 (1–2): 71–109. doi:10.1016/S0304-3975(01)00303-6.

[61] Rényi, Alfréd (1961). "On a problem in information theory". Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei (ภาษาฮังการี). 6: 505–516. MR 0143666.

[62] Høyer, Peter; Neerbek, Jan; Shi, Yaoyun (2002). "Quantum complexities of ordered searching, sorting, and element distinctness". Algorithmica. 34 (4): 429–448. arXiv:quant-ph/0102078. doi:10.1007/s00453-002-0976-3. S2CID 13717616.

[quantumalgo-63] Childs, Andrew M.; Landahl, Andrew J.; Parrilo, Pablo A. (2007). "Quantum algorithms for the ordered search problem via semidefinite programming". Physical Review A. 75 (3). 032335. arXiv:quant-ph/0608161. Bibcode:2007PhRvA..75c2335C. doi:10.1103/PhysRevA.75.032335. S2CID 41539957.

[64] Grover, Lov K. (1996). A fast quantum mechanical algorithm for database search. 28th ACM Symposium on Theory of Computing. Philadelphia, PA. pp. 212–219. arXiv:quant-ph/9605043. doi:10.1145/237814.237866.

[65] Peterson, William Wesley (1957). "Addressing for random-access storage". IBM Journal of Research and Development. 1 (2): 130–146. doi:10.1147/rd.12.0130.

[66] "2ⁿ−1". OEIS A000225 เก็บถาวร 8 มิถุนายน 2016 ที่ เวย์แบ็กแมชชีน. Retrieved 7 May 2016.

[68] Lehmer, Derrick (1960). Teaching combinatorial tricks to a computer. Proceedings of Symposia in Applied Mathematics. Vol. 10. pp. 180–181. doi:10.1090/psapm/010.

[69] Chazelle, Bernard; Guibas, Leonidas J. (1986). "Fractional cascading: I. A data structuring technique" (PDF). Algorithmica. 1 (1–4): 133–162. CiteSeerX 10.1.1.117.8349. doi:10.1007/BF01840440. S2CID 12745042.

[70] Chazelle, Bernard; Guibas, Leonidas J. (1986), "Fractional cascading: II. Applications" (PDF), Algorithmica, 1 (1–4): 163–191, doi:10.1007/BF01840441, S2CID 11232235

[FOOTNOTEBentley2000§4.1_("The_Challenge_of_Binary_Search")-71] Bentley 2000, §4.1 ("The Challenge of Binary Search").

[textbook-72] Pattis, Richard E. (1988). "Textbook errors in binary searching". SIGCSE Bulletin. 20: 190–194. doi:10.1145/52965.53012.

[73] Bloch, Joshua (2 มิถุนายน 2006). "Extra, extra – read all about it: nearly all binary searches and mergesorts are broken". Google Research Blog. เก็บจากแหล่งเดิมเมื่อ 1 เมษายน 2016. สืบค้นเมื่อ 21 เมษายน 2016.

[semisum-74] Ruggieri, Salvatore (2003). "On computing the semi-sum of two integers" (PDF). Information Processing Letters. 87 (2): 67–71. CiteSeerX 10.1.1.13.5631. doi:10.1016/S0020-0190(03)00263-1. เก็บ (PDF)จากแหล่งเดิมเมื่อ 3 กรกฎาคม 2006. สืบค้นเมื่อ 19 มีนาคม 2016.

[FOOTNOTEBentley2000§4.4_("Principles")-75] Bentley 2000, §4.4 ("Principles").

[76] "bsearch – binary search a sorted table". The Open Group Base Specifications (7th ed.). The Open Group. 2013. เก็บจากแหล่งเดิมเมื่อ 21 มีนาคม 2016. สืบค้นเมื่อ 28 มีนาคม 2016.

[FOOTNOTEStroustrup2013945-77] Stroustrup 2013, p. 945.

[78] "std.range - D Programming Language". dlang.org. สืบค้นเมื่อ 2020-04-29.

[79] Unisys (2012), COBOL ANSI-85 programming reference manual, vol. 1, pp. 598–601

[80] "Package sort". The Go Programming Language. เก็บจากแหล่งเดิมเมื่อ 25 เมษายน 2016. สืบค้นเมื่อ 28 เมษายน 2016.

[81] "java.util.Arrays". Java Platform Standard Edition 8 Documentation. Oracle Corporation. เก็บจากแหล่งเดิมเมื่อ 29 เมษายน 2016. สืบค้นเมื่อ 1 พฤษภาคม 2016.

[82] "java.util.Collections". Java Platform Standard Edition 8 Documentation. Oracle Corporation. เก็บจากแหล่งเดิมเมื่อ 23 เมษายน 2016. สืบค้นเมื่อ 1 พฤษภาคม 2016.

[83] "List<T>.BinarySearch method (T)". Microsoft Developer Network. เก็บจากแหล่งเดิมเมื่อ 7 พฤษภาคม 2016. สืบค้นเมื่อ 10 เมษายน 2016.

[84] "NSArray". Mac Developer Library. Apple Inc. เก็บจากแหล่งเดิมเมื่อ 17 เมษายน 2016. สืบค้นเมื่อ 1 พฤษภาคม 2016.

[85] "CFArray". Mac Developer Library. Apple Inc. เก็บจากแหล่งเดิมเมื่อ 20 เมษายน 2016. สืบค้นเมื่อ 1 พฤษภาคม 2016.

[86] "8.6. bisect — Array bisection algorithm". The Python Standard Library. Python Software Foundation. เก็บจากแหล่งเดิมเมื่อ 25 มีนาคม 2018. สืบค้นเมื่อ 26 มีนาคม 2018.

[FOOTNOTEFitzgerald2015152-87] Fitzgerald 2015, p. 152.

[1]

[2]

[3]

[4]

[5]

[a]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[b]

[17]

[c]

[18]

[19]

[20]

[21]

[22]

[d]

[24]

[25]

[26]

[27]

[e]

[29]

[30]

[31]

[32]

[f]

[34]

[35]

[36]

[37]

[g]

[h]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

[57]

[i]

[59]

[60]

[61]

[62]

[63]

[64]

[65]

[66]

[67]

[68]

[69]

[70]

[71]

[72]

[73]

[74]

[75]

[76]

[77]

[78]

[23]

[28]

[33]

[38]

[58]