ผลต่างระหว่างรุ่นของ "การค้นหาแบบทวิภาค"
เพิ่มเนื้อหาเรื่อง Variations: uniform binar search, exponential search, interpolation search, fractional search |
เพิ่มเนื้อหาเรื่อง variations: Generalization to graphs, Noisy binary search, Quantum binary search |
||
บรรทัด 302: | บรรทัด 302: | ||
แต่เดิม การเรียงซ้อนแบบเศษส่วนถูกพัฒนามาเพื่อแก้ปัญหาเกี่ยวกับ{{ill|เรขาคณิตเชิงคำนวณ|en|computational geometry}}ได้อย่างมีประสิทธิภาพ ปัจจุบันการเรียงซ้อนแบบเศษส่วนยังถูกนำไปประยุกต์ใช้ในด้านอื่น ๆ อีก เช่น ใน[[การทำเหมืองข้อมูล]] และใน[[อินเทอร์เน็ตโพรโทคอล]]<ref name="ChazelleLiu2001" /> |
แต่เดิม การเรียงซ้อนแบบเศษส่วนถูกพัฒนามาเพื่อแก้ปัญหาเกี่ยวกับ{{ill|เรขาคณิตเชิงคำนวณ|en|computational geometry}}ได้อย่างมีประสิทธิภาพ ปัจจุบันการเรียงซ้อนแบบเศษส่วนยังถูกนำไปประยุกต์ใช้ในด้านอื่น ๆ อีก เช่น ใน[[การทำเหมืองข้อมูล]] และใน[[อินเทอร์เน็ตโพรโทคอล]]<ref name="ChazelleLiu2001" /> |
||
===การประยุกต์ใช้ในกราฟ=== |
|||
การค้นหาแบบทวิภาคถูกนำมาใช้กับกราฟบางประเภท โดยค่าเป้าหมายนั้นจะถูกเก็บในรูปของโหนดแทนสมาชิกในแถวลำดับ ต้นไม้ค้นหาแบบทวิภาคคือหนึ่งในตัวอย่างนั้น เมื่อโหนดของต้นไม้ถูกตรวจสอบ ขั้นตอนวิธีจะได้รู้ว่าโหนดนั้นคือเป้าหมายหรือไม่ หรือค่าเป้าหมายจะอยู่ในต้นไม้ย่อยต้นไหน อย่างไรก็ตาม การค้นหาแบบทวิภาคสามารถนำไปใช้ได้ในกราฟอื่นได้อีก เช่น ในกราฟแบบไม่มีทิศทางและถ่วงน้ำหนักเชิงบวก (an undirected, positively weighted graph) ขั้นตอนวิธีจะทราบจากการตรวจสอบโหนดใด ๆ ว่า โหนดนั้นมีค่าเท่ากับค่าเป้าหมายหรือไม่ ถ้าไม่แล้วเส้นเชื่อม (incident edge) ใดที่เป็นเส้นทางที่สั้นที่สุดจากโหนดที่กำลังตรวจสอบอยู่ไปยังโหนดเป้าหมาย เช่นเดียวกัน ต้นไม้ค้นหาแบบทวิภาคจะพิจารณาเส้นเชื่อมไปยังต้นไม้ย่อยฝั่งซ้ายและฝั่งขวาเมื่อโหนดที่กำลังตรวจสอบอยู่มีค่าไม่เท่ากับค่าเป้าหมาย สำหรับกราฟแบบไม่มีทิศทางและถ่วงน้ำหนักเชิงบวกทุกกราฟ ในกรณีที่แย่ที่สุด ขั้นตอนวิธีจะใช้การตรวจสอบทั้งหมด <math>O(\log n)</math> ครั้งจนกว่าจะเจอโหนดเป้าหมาย<ref>{{cite conference|last1=Emamjomeh-Zadeh|first1=Ehsan|last2=Kempe|first2=David|last3=Singhal|first3=Vikrant|title=Deterministic and probabilistic binary search in graphs|date=2016|pages=519–532|conference=48th [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]]|arxiv=1503.00805|doi=10.1145/2897518.2897656}}</ref> |
|||
===Noisy binary search=== |
|||
[[File:Noisy binary search.svg|thumb|upright=1.5|ใน noisy binary search มีความน่าจะเป็นที่การเปรียบเทียบนั้นจะให้ผลลัพธ์ที่ไม่ถูกต้อง]] |
|||
ขั้นตอนวิธีของ Noisy binary search ถูกใช้แก้ปัญหาในกรณีที่ขั้นตอนวิธีไม่สามารถเปรียบเทียบค่าของสมาชิกในแถวลำดับได้อย่างน่าเชื่อถือ ในการเปรียบเทียบแต่ละคู่สมาชิกนั้นมีโอกาสที่ขั้นตอนวิธีจะเปรียบเทียบได้ผลลัพธ์ที่ไม่ถูกต้อง Noisy binary search สามารถค้นหาตำแหน่งที่ถูกต้องของเป้าหมายได้โดยมีความน่าจะเป็นที่ควบคุมความน่าเชื่อถือของผลลัพธ์ที่ได้ ทุก ๆ Noisy binary search จะต้องมีการเปรียบเทียบอย่างน้อย <math>(1 - \tau)\frac{\log_2 (n)}{H(p)} - \frac{10}{H(p)}</math> ครั้งโดยเฉลี่ย โดยที่ <math>H(p) = -p \log_2 (p) - (1 - p) \log_2 (1 - p)</math><!-- Attribution of LaTeX code: see history of https://en.wikipedia.org/wiki/Binary_entropy_function --> คือ {{ill|binary entropy function|en|binary entropy function}} และ <math>\tau</math> คือ ความน่าจะเป็นที่กระบวนการนั้นจะคืนค่าตำแหน่งเป้าหมายที่ไม่ถูกต้อง<ref>{{cite conference |last1=Ben-Or |first1=Michael |last2=Hassidim |first2=Avinatan |title=The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well) |date=2008 |book-title=49th [[Annual IEEE Symposium on Foundations of Computer Science|Symposium on Foundations of Computer Science]] |pages=221–230 |doi=10.1109/FOCS.2008.58 |url=http://www2.lns.mit.edu/~avinatan/research/search-full.pdf |isbn=978-0-7695-3436-7}}</ref><ref name="pelc1989">{{cite journal|last1=Pelc|first1=Andrzej|title=Searching with known error probability|journal=Theoretical Computer Science|date=1989|volume=63|issue=2|pages=185–202|doi=10.1016/0304-3975(89)90077-7|doi-access=free}}</ref><ref>{{cite conference|last1=Rivest|first1=Ronald L.|last2=Meyer|first2=Albert R.|last3=Kleitman|first3=Daniel J.|last4=Winklmann|first4=K.|author-link1=Ronald Rivest|author-link2=Albert R. Meyer|author-link3=Daniel Kleitman|title=Coping with errors in binary search procedures|conference=10th [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]]|doi=10.1145/800133.804351}}</ref> ปัญหา noisy binary search เช่น {{ill|เกมของอุลาม|en|Ulam's game}} <ref>{{cite journal|last1=Pelc|first1=Andrzej|title=Searching games with errors—fifty years of coping with liars|journal=Theoretical Computer Science|date=2002|volume=270|issue=1–2|pages=71–109|doi=10.1016/S0304-3975(01)00303-6|doi-access=free}}</ref> คือการถาม{{ill|คำถามยี่สิบข้อ|en|twenty questions}}ที่แตกต่างกันเพื่อทายวัตถุหรือตัวเลขนั้น โดยคำตอบที่ได้รับจากคำถามนั้นอาจไม่ถูกต้อง<ref>{{Cite journal | last1=Rényi | first1=Alfréd | title=On a problem in information theory | language=hu | mr=0143666 | year=1961 | journal=Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei| volume=6 | pages=505–516}}</ref> |
|||
===การค้นหาแบบทวิภาคควอนตัม=== |
|||
การดำเนินการค้นหาแบบทวิภาคในคอมพิวเตอร์แบบดั้งเดิมจะใช้การวนซ้ำทั้งหมด <math display="inline">\lfloor \log_2 n + 1 \rfloor</math> ครั้งในกรณีที่แย่ที่สุด {{ill|ขั้นตอนวิธีควอนตัม|en|quantum algorithm}}สำหรับการค้นหาแบบทวิภาคจะมีการตรวจสอบทั้งหมด <math display="inline">\log_2 n</math> ครั้ง (แทนจำนวนการวนซ้ำในกระบวนการดั้งเดิม) แต่ตัวประกอบคงที่ (constant factor) จะมีค่าน้อยกว่าหนึ่ง ทำให้มีค่าความซับซ้อนของเวลาน้อยลงเมื่อทำงานใน{{ill|คอมพิวเตอร์เชิงควอนตัม|en|quantum computing}} กระบวนการของการค้นหาแบบทวิภาคควอนตัมที่แท้จริง หรือคือกระบวนการที่จะคืนค่าผลลัพธ์ที่ถูกต้องเสมอ จะต้องมีการตรวจสอบอย่างน้อย <math display="inline">\frac{1}{\pi}(\ln n - 1) \approx 0.22 \log_2 n</math> ครั้งในกรณีที่แย่ที่สุด เมื่อ <math display="inline">\ln</math> คือ [[ลอการิทึมธรรมชาติ]]<ref>{{cite journal|last1=Høyer|first1=Peter|last2=Neerbek|first2=Jan|last3=Shi|first3=Yaoyun|s2cid=13717616|title=Quantum complexities of ordered searching, sorting, and element distinctness|journal=[[Algorithmica]]|date=2002|volume=34|issue=4|pages=429–448|doi=10.1007/s00453-002-0976-3|arxiv=quant-ph/0102078}}</ref> กระบวนการของการค้นหาแบบทวิภาคควอนตัมที่แท้จริงบางอันดำเนินการตรวจสอบทั้งหมด <math display="inline">4 \log_{605} n \approx 0.433 \log_2 n</math> ครั้งในกรณีที่แย่ที่สุด<ref name="quantumalgo">{{cite journal|last1=Childs|first1=Andrew M.|last2=Landahl|first2=Andrew J.|last3=Parrilo|first3=Pablo A.|s2cid=41539957|title=Quantum algorithms for the ordered search problem via semidefinite programming|journal=Physical Review A|date=2007|volume=75|issue=3|at=032335|doi=10.1103/PhysRevA.75.032335|arxiv=quant-ph/0608161|bibcode=2007PhRvA..75c2335C}}</ref> ในทางตรงกันข้าม {{ill|ขั้นตอนวิธีของโกรเวอร์|en|Grover's algorithm}} คือขั้นตอนวิธีควอนตัมที่ดีที่สุดสำหรับการค้นหาสมาชิกในรายการแบบไม่มีลำดับ โดยใช้การตรวจสอบทั้งหมด <math>O(\sqrt{n})</math> ครั้ง<ref>{{cite conference |last1=Grover |first1=Lov K. | author-link=Lov Grover | title=A fast quantum mechanical algorithm for database search | conference=28th [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]] |pages=212–219|date=1996| location=Philadelphia, PA | doi=10.1145/237814.237866| arxiv=quant-ph/9605043}}</ref> |
|||
== การใช้ในงานทั่วไป == |
== การใช้ในงานทั่วไป == |
รุ่นแก้ไขเมื่อ 00:30, 7 สิงหาคม 2565
ตัวอย่างการค้นหาแบบทวิภาค โดยมี 7 เป็นค่าเป้าหมาย | |
ประเภท | ขั้นตอนวิธีการค้นหา |
---|---|
โครงสร้างข้อมูล | แถวลำดับ |
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด | |
ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด | |
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป | |
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด | |
ในสาขาวิทยาการคอมพิวเตอร์ การค้นหาแบบทวิภาค (อังกฤษ: binary search, half-interval search หรือ bisection search) เป็นขั้นตอนวิธีเพื่อหาตำแหน่งของค่าที่ต้องการ (ข้อมูลนำเข้า หรือ "key") ที่ใช้ในแถวลำดับที่ได้มีการเรียงลำดับข้อมูลแล้ว[1][2] ขั้นตอนวิธีจะเริ่มจากเปรียบเทียบข้อมูลที่นำเข้ากับข้อมูลที่อยู่ตรงกลางของแถวลำดับ ถ้าข้อมูลมีค่าเท่ากันแสดงว่าพบ "คีย์" ที่ต้องการ อาจจะทำการคืนค่าตำแหน่งหรือในที่นี้คือ ดัชนี (index) กลับไป มิฉะนั้นถ้าค่าของข้อมูลนำเข้าที่ต้องการค้นหามีการน้อยกว่าค่าตรงกลางของแถวลำดับ ก็จะทำขั้นตอนวิธีนี้อีกครั้งแต่เปลี่ยนมาค้นหาในแถวลำดับย่อยของแถวลำดับที่ต้องการค้นหาโดยแถวลำดับย่อยจะมีจุดสิ้นสุดที่ตรงกลางของแถวลำดับหลัก หรือถ้าข้อมูลที่ต้องการค้นหามีค่ามากกว่าแล้วจะค้นหาในแถวลำดับย่อยเช่นกันแต่ย้ายจุดเริ่มต้นมาที่ตรงกลางของแถวลำดับหลัก เมื่อทำไปจนแถวลำดับไม่มีสมาชิกอยู่หรือจุดเริ่มต้นมากกว่าจุดสิ้นสุด แสดงว่าไม่มีสมาชิกในแถวลำดับตัวใดที่มีค่าเท่ากับข้อมูลนำเข้าที่ต้องการค้นหา อาจจะคืนค่าว่า "ไม่พบ"
ในกรณีแย่ที่สุด การค้นหาแบบทวิภาคจะดำเนินงานโดยมีความซับซ้อนของเวลาในรูปลอการิทึม ซึ่งจะมีค่า เมื่อ คือจำนวนแถวลำดับของข้อมูล[3] การค้นหาแบบทวิภาคจะใช้เวลาดำเนินงานน้อยกว่าการค้นหาแบบเชิงเส้น ยกเว้นในกรณีที่แถวลำดับมีจำนวนน้อย อย่างไรก็ตาม แถวลำดับนั้นจะต้องมีการเรียงลำดับข้อมูลก่อนจึงจะสามารถดำเนินการค้นหาแบบทวิภาคได้ นอกจากการค้นหาแบบทวิภาคแล้ว ยังมีโครงสร้างข้อมูลเฉพาะแบบอื่น ๆ ที่ถูกออกแบบมาเพื่อให้สามารถค้นหาได้อย่างรวดเร็ว เช่น ตารางแฮช ซึ่งสามารถนำมาใช้ในการค้นหาข้อมูลได้มีประสิทธิภาพกว่าการค้นหาแบบทวิภาค อย่างไรก็ตาม การค้นหาแบบทวิภาคยังคงสามารถใช้แก้ปัญหาได้อย่างกว้างขวาง เช่น การหาข้อมูลที่มีขนาดเล็กที่สุดหรือใหญ่ที่สุดตัวถัดไปในแถวลำดับ ถึงแม้ข้อมูลนั้นจะไม่ปรากฏในแถวลำดับก็ตาม
การค้นหาแบบทวิภาคมีหลากหลายรูปแบบ โดยเฉพาะอย่างยิ่ง การเรียงซ้อนแบบเศษส่วน ที่ช่วยเพิ่มความเร็วในการค้นหาแบบทวิภาคสำหรับข้อมูลที่มีค่าเดียวกันในหลายแถวลำดับ การเรียงซ้อนแบบเศษส่วนช่วยแก้ปัญหาเกี่ยวกับเรขาคณิตเชิงคำนวณ และด้านอื่น ๆ จำนวนมากได้อย่างมีประสิทธิภาพ นอกจากนั้นยังมีการค้นหาแบบเอกซ์โพเนนเชียล ที่ช่วยขยายขอบเขตการค้นหาแบบทวิภาคได้อย่างไม่จำกัด และต้นไม้ค้นหาแบบทวิภาคและต้นไม้แบบบีซึ่งเป็นโครงสร้างข้อมูลที่อ้างอิงมาจากการค้นหาแบบทวิภาค
การค้นหาแบบทวิภาคจะแบ่งครึ่งชุดข้อมูลที่ต้องการค้นหา ดังนั้นจึงจัดให้การค้นหาแบบทวิภาคเป็นขั้นตอนวิธีแบ่งแยกและเอาชนะ และขั้นตอนวิธีการค้นหา
ขั้นตอนวิธี
การค้นหาแบบทวิภาคสามารถดำเนินการได้ในแถวลำดับที่มีการเรียงลำดับข้อมูลแล้ว โดยจะเริ่มจากการเปรียบเทียบค่าของข้อมูลที่อยู่ตรงกลางของแถวลำดับกับค่าเป้าหมาย หากข้อมูลตรงกลางนั้นมีค่าเท่ากับค่าเป้าหมาย จะทำการคืนค่าตำแหน่งในแถวลำดับของข้อมูลนั้น แต่หากข้อมูลตรงกลางมีค่าน้อยกว่าค่าเป้าหมาย การค้นหาแบบทวิภาคจะถูกดำเนินการต่อไปกับแถวลำดับครึ่งหลัง ในทำนองเดียวกัน หากข้อมูลตรงกลางมีค่ามากกว่าค่าเป้าหมาย การค้นหาก็จะถูกดำเนินการในแถวลำดับครึ่งหน้า ด้วยขั้นตอนวิธีนี้ทำให้สามารถกำจัดข้อมูลได้ครึ่งหนึ่งเสมอในทุกการวนซ้ำ[4]
แบบเวียนเกิด
การค้นหาแบบทวิภาคสามารถใช้การเรียกซ้ำได้ โดยมีสิ่งที่ต้องการคือพารามิเตอร์อันได้แก่ แถวลำดับที่มีการเรียงลำดับมาแล้ว (ในต้วอย่างจะเป็นการเรียงลำดับจากน้อยไปมาก) ซึ่งสามารถอ้างถึงแถวลำดับตรงกลางได้ด้วยดัชนี (index) ต้น และปลายของแถวลำดับ ซึ่งพารามิเตอร์เหล่านี้จะทำให้สามารถเรียกฟังก์ชันแบบเรียกซ้ำได้ และโดยขั้นตอนวิธีแล้ว การเขียนการค้นหาแบบทวิภาคด้วยการเวียนเกิดหรือเรียกซ้ำนั้น คอมไพเลอร์จะไม่มีการสร้างกองซ้อนกองใหม่ขึ้นมา โดยจะใช้เพียงกองเดียวเท่านั้น พิจารณาตัวแปร คือแถวลำดับที่ต้องการค้นหา, คือค่าของตัวแปรที่ต้องการค้นหาในแถวลำดับ , คือดัชนีของต้นแถวลำดับ , คือดัชนีของปลายแถวลำดับ และ คือจำนวนแถวลำดับของข้อมูล
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
การวนซ้ำ
กำหนดให้แถวลำดับ มีสมาชิก ตัว โดยแต่ละตัวมีค่าหรือระเบียน ซึ่งถูกเรียงลำดับข้อมูลเพื่อให้ มีดัชนีของต้นแถวลำดับ และดัชนีปลายแถวลำดับ และกำหนดค่าเป้าหมาย ซับรูทีนต่อไปนี้ใช้การค้นหาแบบทวิภาคเพื่อหาดัชนีตำแหน่งของ ใน [4]
- กำหนดให้ และ
- ถ้า แล้วการค้นหาจะสิ้นสุดลง และคืนค่าว่าค้นหาไม่สำเร็จ
- กำหนดให้ (ตำแหน่งกึ่งกลางของแถวลำดับที่สนใจ) มีค่าเท่ากับฟังก์ชันพื้นของ หรือหมายถึงจำนวนเต็มที่มากที่สุดที่มีค่าน้อยกว่าหรือเท่ากับ
- ถ้า แล้วกำหนดให้ และกลับไปยังขั้นตอนที่ 2
- ถ้า แล้วกำหนดให้ และกลับไปยังขั้นตอนที่ 2
- ถ้า แสดงว่าการค้นหาเสร็จสิ้น คืนค่า
ขั้นตอนการวนซ้ำนี้จะติดตามขอบเขตการค้นหาด้วยตัวแปร และ และสามารถแสดงผลในรูปรหัสเทียมได้ดังตัวอย่างด้านล่าง โดยชื่อตัวแปรที่ใช้จะคงเดิมเหมือนตัวอย่างด้านบน floor
คือ ฟังก์ชันพื้น และ unsuccessful
แทนค่าเฉพาะที่สื่อถึงความล้มเหลวของการค้นหา[4]
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
ในอีกทางเลือกหนึ่ง ขั้นตอนวิธีนี้อาจใช้ค่าฟังก์ชันเพดานของ ซึ่งจะทำให้ผลลัพธ์เปลี่ยนแปลงไปหากค่าเป้าหมายปรากฏในแถวลำดับมากกว่า 1 ครั้ง
ขั้นตอนทางเลือก
ในขั้นตอนวิธีด้านบนอาศัยการตรวจสอบในทุก ๆ การวนซ้ำว่าค่ากลาง () มีค่าเท่ากับค่าเป้าหมายที่ต้องการ () หรือไม่ กระบวนการบางอย่างได้ละเว้นวิธีการตรวจสอบนี้ในแต่ละการวนซ้ำ ทำให้ขั้นตอนวิธีนั้นจะทำการตรวจสอบนี้เฉพาะเมื่อการวนซ้ำครั้งนั้นเหลือสมาชิกเพียงตัวเดียว (เมื่อ ) ส่งผลให้ใช้เวลาน้อยลงในระหว่างรอบการวนซ้ำ เนื่องจากชุดเปรียบเทียบจะถูกกำจัดทิ้งหนึ่งชุดในหนึ่งรอบการวนซ้ำ ในขณะที่มีจำนวนรอบการวนซ้ำเพิ่มขึ้นเพียงหนึ่งครั้งโดยเฉลี่ยเท่านั้น[5]
Hermann Bottenbruch ได้ตีพิมพ์กระบวนการแรกที่ละเว้นวิธีการตรวจสอบนี้ในปีค.ศ. 1962[5][6]
- กำหนดให้ และ
- เมื่อ
- กำหนดให้ (ตำแหน่งกึ่งกลางของแถวลำดับที่สนใจ) มีค่าเท่ากับฟังก์ชันเพดานของ หรือหมายถึงจำนวนเต็มที่น้อยที่สุดที่มีค่ามากกว่าหรือเท่ากับ
- ถ้า แล้วกำหนดให้
- มิฉะนั้น ถ้า แล้วกำหนดให้
- เมื่อ การค้นหาจะเสร็จสิ้นลง ถ้า แล้วจะคืนค่า มิฉะนั้นจะคืนค่าว่าไม่สำเร็จ
เมื่อ 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
สมาชิกที่ซ้ำกัน
การค้นหาแบบทวิภาคอาจคืนค่าดัชนีใด ๆ ของสมาชิกที่มีค่าเท่ากับค่าเป้าหมาย ถึงแม้ในแถวลำดับจะมีสมาชิกที่มีค่าซ้ำกัน ยกตัวอย่างเช่น ถ้าแถวลำดับที่ต้องการค้นหาคือ และค่าเป้าหมายคือ แล้วขั้นตอนวิธีอาจคืนค่าที่ถูกต้องได้ทั้งตำแหน่งที่ 4 (ดัชนีที่ 3) หรือตำแหน่งที่ 5 (ดัชนีที่ 4) ซึ่งกระบวนการปกติมักจะคืนค่าตำแหน่งที่ 4 (ดัชนีที่ 3) แต่ก็ไม่ใช่เสมอไปที่ค่าที่ถูกคืนจะเป็นตำแหน่งแรกของสมาชิกที่ซ้ำกัน อย่างไรก็ตาม ในบางครั้งการหาค่าเป้าหมายที่มีสมาชิกที่ซ้ำกันในแถวลำดับก็จำเป็นที่จะต้องหาสมาชิกขอบซ้ายสุดหรือขวาสุด ในตัวอย่างข้างต้น สมาชิกซ้ายสุดที่มีค่าเท่ากับ 4 คือสมาชิกตำแหน่งที่ 4 และสมาชิกขวาสุดที่มีค่าเท่ากับ 4 คือสมาชิกตำแหน่งที่ 5 ซึ่งการค้นหาโดยใช้ขั้นตอนทางเลือกจะคืนค่าดัชนีของสมาชิกขวาสุด (ถ้ามี)[6]
กระบวนการหาสมาชิกซ้ายสุด
ในการจะหาสมาชิกซ้ายสุดสามารถทำได้ดังนี้:[7]
- กำหนดให้ และ
- เมื่อ
- กำหนดให้ (ตำแหน่งกึ่งกลางของแถวลำดับที่สนใจ) มีค่าเท่ากับฟังก์ชันพื้นของ หรือหมายถึงจำนวนเต็มที่มากที่สุดที่มีค่าน้อยกว่าหรือเท่ากับ
- ถ้า แล้วกำหนดให้
- มิฉะนั้น ถ้า แล้วกำหนดให้
- คืนค่า
ถ้า และ แล้ว คือสมาชิกซ้ายสุดที่มีค่าเท่ากับ ในกรณีที่ไม่มีสมาชิกใดในแถวลำดับที่มีค่าเท่ากับ จะถือว่าเป็นอันดับของ ในแถวลำดับ หรือคือจำนวนสมาชิกทั้งหมดในแถวลำดับที่มีค่าน้อยกว่า
เมื่อ 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
กระบวนการหาสมาชิกขวาสุด
ในการจะหาสมาชิกขวาสุดสามารถทำได้ดังนี้:[7]
- กำหนดให้ และ
- เมื่อ
- กำหนดให้ (ตำแหน่งกึ่งกลางของแถวลำดับที่สนใจ) มีค่าเท่ากับฟังก์ชันพื้นของ หรือหมายถึงจำนวนเต็มที่มากที่สุดที่มีค่าน้อยกว่าหรือเท่ากับ
- ถ้า แล้วกำหนดให้
- มิฉะนั้น ถ้า แล้วกำหนดให้
- คืนค่า
ถ้า และ แล้ว คือสมาชิกขวาสุดที่มีค่าเท่ากับ ในกรณีที่ไม่มีสมาชิกใดในแถวลำดับที่มีค่าเท่ากับ จะเป็นจำนวนสมาชิกทั้งหมดในแถวลำดับที่มีค่ามากกว่ากว่า
เมื่อ 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
การหาคู่ที่ใกล้เคียง
กระบวนการด้านต้นจะดำเนินการหาคู่ที่ถูกต้องซึ่งคือตำแหน่งของสมาชิกที่มีค่าเท่ากับค่าเป้าหมายเท่านั้น อย่างไรก็ตาม การขยายขอบเขตการค้นหาแบบทวิภาคเพื่อดำเนินการหาคู่ที่ใกล้เคียงก็สามารถทำได้โดยง่าย เพราะการค้นหาแบบทวิภาคจะดำเนินการในแถวลำดับที่เรียงลำดับแล้ว ยกตัวอย่างเช่น การค้นหาแบบทวิภาคสามารถใช้เพื่อคำนวณอันดับ (จำนวนสมาชิกที่มีค่าน้อยกว่า) สมาชิกก่อนหน้า (predecessor) สมาชิกตามหลัง (successor) และเพื่อนบ้านใกล้สุดของค่าที่กำหนด ซึ่งการหาขอบเขต หรือคือการหาจำนวนสมาชิกระหว่างค่าสองค่าก็สามารถดำเนินการได้ด้วยการหาอันดับ 2 ครั้ง[8]
- การหาอันดับสามารถดำเนินการได้ด้วยกระบวนการหาสมาชิกซ้ายสุด โดยจะคืนค่าจำนวนสมาชิกที่มีค่าน้อยกว่าค่าเป้าหมาย[8]
- การหาสมาชิกก่อนหน้าสามารถดำเนินการได้ด้วยการหาอันดับ ถ้าอันดับของค่าเป้าหมายคือ แล้วอันดับของสมาชิกก่อนหน้าคือ [9]
- การหาสมาชิกตามหลังสามารถดำเนินการได้ด้วยกระบวนการหาสมาชิกขวาสุด ถ้ากระบวนการนั้นคืนค่า แล้วอันดับของสมาชิกตามหลังคือ
- เพื่อนบ้านใกล้สุดของค่าเป้าหมายอาจเป็นสมาชิกก่อนหน้าหรือสมาชิกตามหลังก็ได้ ขึ้นอยู่กับว่าค่าไหนใกล้เคียงค่าเป้าหมายมากกว่ากัน
- การหาขอบเขตสามารถทำได้อย่างตรงไปตรงมา[9] โดยเมื่อรู้อันดับของค่าทั้งสอง (สมาชิกก่อนหน้าและสมาชิกตามหลัง) แล้ว จำนวนสมาชิกที่มีค่ามากกว่าหรือเท่ากับค่าสมาชิกก่อนหน้าและน้อยกว่าค่าสมาชิกตามหลังจะเป็นผลต่างระหว่างอันดับของค่าทั้งสอง การนับแบบนี้สามารถมีค่าเพิ่มขึ้นหรือลดลง 1 ค่าได้ขึ้นอยู่กับว่าจุดปลายของขอบเขตควรถูกพิจารณาเป็นส่วนหนึ่งของขอบเขตหรือไม่ และแถวลำดับมีข้อมูลที่เข้าคู่กับจุดปลายเหล่านั้นหรือไม่[10]
ประสิทธิภาพ
ในแง่ของจำนวนการเปรียบเทียบ ประสิทธิภาพของการค้นหาแบบทวิภาคสามารถวิเคราะห์ได้จากการดูการทำงานของต้นไม้แบบทวิภาค โดยปมรากของต้นไม้คือค่ากลางของแถวลำดับ ค่ากลางของครึ่งแถวล่างคือปมลูกด้านซ้ายของราก และค่ากลางของครึ่งแถวบนคือปมลูกด้านขวาของราก ส่วนที่เหลือของต้นไม้ก็มีโครงสร้างที่คล้ายคลึงกับรูปแบบที่กล่าวไปด้านต้น คือ เริ่มจากปมราก การตัดสินใจว่าจะผ่านต้นไม้ย่อยด้านซ้ายหรือขวาจะขึ้นอยู่กับว่า ค่าเป้าหมายมีค่าน้อยหรือมากกว่าปมที่กำลังตัดสินใจอยู่[3][11]
ในกรณีที่แย่ที่สุด การค้นหาแบบทวิภาคจะถูกวนซ้ำทั้งหมด รอบการเปรียบเทียบ เมื่อ คือสัญลักษณ์ที่แสดงถึงฟังก์ชันพื้นที่ให้ผลลัพธ์เป็นจำนวนเต็มที่มากที่สุดที่น้อยกว่าหรือเท่ากับอาร์กิวเมนต์ (argument) และ คือลอการิทึมฐานสอง เนื่องจากกรณีที่แย่ที่สุดจะเกิดขึ้นเมื่อการค้นหาดำเนินการไปถึงชั้นล่างสุดของต้นไม้ ซึ่งต้นไม้แบบทวิภาคจะมีทั้งหมด ชั้นเสมอ
กรณีที่แย่ที่สุดอาจเกิดขึ้นได้เช่นกันในกรณีที่ค่าเป้าหมายไม่อยู่ในแถวลำดับ ถ้า มีค่าน้อยกว่ากำลังของสองอยู่หนึ่งค่า แล้วกรณีนี้จะเป็นจริงเสมอ มิฉะนั้น การค้นหาอาจวนซ้ำ รอบเมื่อการค้นหาดำเนินการไปถึงชั้นล่างสุดของต้นไม้ อย่างไรก็ตาม หากการค้นหาสิ้นสุดที่ชั้นที่ลึกที่สุดเป็นอันดับสองของต้นไม้ แล้วการค้นหาจะวนซ้ำทั้งหมด รอบ ซึ่งน้อยกว่าจำนวนการวนซ้ำของกรณีที่แย่ที่สุดอยู่หนึ่งครั้ง[12]
หากสมมุติให้สมาชิกทุกตัวมีโอกาสที่จะถูกค้นหาเท่ากัน แล้วการค้นหาแบบทวิภาคจะวนซ้ำทั้งหมด รอบโดยเฉลี่ย เมื่อค่าเป้าหมายมีอยู่ในแถวลำดับ ซึ่งจะประมาณเท่ากับ รอบ ถ้าค่าเป้าหมายไม่อยู่ในแถวลำดับ แล้วการค้นหาแบบทวิภาคจะวนซ้ำ รอบโดยเฉลี่ย โดยสมมุติให้ขอบเขตระหว่างและนอกเหนือจากสมาชิกมีโอกาสที่จะถูกค้นหาเท่ากัน[11]
ในกรณีที่ดีที่สุด หรือเมื่อค่าเป้าหมายคือค่ากลางของแถวลำดับ ตำแหน่งของค่าเป้าหมายจะถูกคืนค่าหลังจากการวนซ้ำเพียงหนึ่งรอบ[13]
ในแง่ของการวนซ้ำ ไม่มีขั้นตอนวิธีการค้นหาใดที่ทำการค้นหาโดยการเปรียบเทียบสมาชิกในแถวลำดับแล้วจะมีประสิทธิภาพทั้งในกรณีเฉลี่ยและกรณีที่แย่ที่สุดดีกว่าการค้นหาแบบทวิภาค ต้นไม้ตัดสินใจแสดงให้เห็นว่าการค้นหาแบบทวิภาคมีจำนวนชั้นน้อยที่สุดเท่าที่จะเป็นไปได้เมื่อจำนวนชั้นที่อยู่สูงกว่าชั้นล่างสุดทั้งหมดของต้นไม้ถูกเติมเต็มหมดแล้ว มิฉะนั้น ขั้นตอนวิธีการค้นหาสามารถกำจัดสมาชิกในหนึ่งการวนซ้ำได้เล็กน้อย ซึ่งจะเป็นการเพิ่มจำนวนการวนซ้ำที่จำเป็นทั้งในกรณีเฉลี่ยและกรณีที่แย่ที่สุด และนั่นจะเป็นกรณีสำหรับขั้นตอนวิธีการค้นหาแบบอื่น ๆ ที่อาศัยการเปรียบเทียบสมาชิก ถึงแม้ว่าขั้นตอนวิธีการค้นหาอื่นอาจดำเนินการได้เร็วกว่าสำหรับค่าเป้าหมายบางค่า แต่ประสิทธิภาพโดยเฉลี่ยก็ยังคงน้อยกว่าการค้นหาแบบทวิภาค เนื่องจากการค้นหาแบบทวิภาคจะมีการแบ่งครึ่งแถวลำดับเสมอ ดังนั้นจึงจะมั่นใจได้ว่าขนาดของแถวลำดับย่อยที่ถูกแบ่งทั้งสองแถวจะมีค่าใกล้เคียงกันมากที่สุด[11] อย่างไรก็ตาม การค้นหาแบบทวิภาคจะสามารถดำเนินการได้ในแถวลำดับที่มีการเรียงลำดับแล้วเท่านั้น
ความซับซ้อนด้านพื้นที่
การค้นหาแบบทวิภาคจำเป็นต้องใช้พอยน์เตอร์ (pointer) 3 อันในการเก็บตำแหน่งที่อยู่ของตัวแปร โดยอาจเป็นดัชนีของแถวลำดับ หรือพอยน์เตอร์ไปยังตำแหน่งที่อยู่หน่วยความจำ โดยไม่คำนึงถึงขนาดของแถวลำดับ ดังนั้น ความซับซ้อนด้านพื้นที่ของการค้นหาแบบทวิภาคคือ ในรูปแบบการคำนวณ word RAM
แหล่งที่มาของกรณีเฉลี่ย
จำนวนการวนซ้ำโดยเฉลี่ยของการค้นหาแบบทวิภาคขึ้นอยู่กับความน่าจะเป็นที่สมาชิกแต่ละตัวในแถวลำดับจะถูกค้นหา กรณีเฉลี่ยจะแตกต่างกันไปสำหรับการค้นหาที่สำเร็จและไม่สำเร็จ สำหรับการค้นหาที่สำเร็จจะถูกอนุมานว่าสมาชิกแต่ละตัวในแถวลำดับมีโอกาสที่จะถูกค้นหาเท่ากัน สำหรับการค้นหาที่ไม่สำเร็จจะถูกอนุมานว่าช่วงระหว่างและนอกเหนือจากสมาชิกมีโอกาสที่จะถูกค้นหาเท่ากัน กรณีเฉลี่ยสำหรับการค้นที่สำเร็จคือจำนวนการวนซ้ำเพื่อค้นหาสมาชิกทุกตัวในครั้งเดียว หารด้วย ซึ่งก็คือจำนวนสมาชิกในแถวลำดับ ส่วนกรณีเฉลี่ยสำหรับการค้นหาที่ไม่สำเร็จคือจำนวนการวนซ้ำเพื่อค้นหาสมาชิกในทุกช่วงในครั้งเดียว หารด้วยจำนวน ช่วง[11]
การค้าหาที่สำเร็จ
ในต้นไม้แบบทวิภาค การค้นหาที่สำเร็จสามารถถูกอธิบายได้ด้วยเส้นทางจากรากถึงปมเป้าหมาย เรียกว่า เส้นทางภายใน (internal path) ความยาวของเส้นทางจะเท่ากับจำนวนขอบ (เส้นเชื่อมต่อระหว่างปม) ที่เส้นทางเดินทางผ่าน เมื่อกำหนดให้เส้นทางที่สอดคล้องนั้นมีความยาว จำนวนการวนซ้ำในการค้นจะเท่ากับ โดยนับการวนซ้ำรอบแรกด้วย ความยาวของเส้นทางภายในจะเท่ากับผลรวมของความยาวของเส้นทางภายในที่เฉพาะ เนื่องจากจะมีเพียงหนึ่งเส้นทางที่เดินทางจากรากไปยังปมเดี่ยวใด ๆ ดังนั้น เส้นทางภายในแต่ละเส้นจะเป็นตัวแทนของการค้นหาสมาชิกแต่ละตัวโดยเฉพาะ ถ้ามีสมาชิกทั้งหมด ตัว (ซึ่ง จะเป็นจำนวนเต็มบวก) และความยาวของเส้นทางภายในคือ แล้วจำนวนการวนซ้ำโดยเฉลี่ยสำหรับการค้นหาที่สำเร็จคือ โดยจำนวนการวนซ้ำ 1 ครั้งที่ถูกบวกเข้าไปเพิ่มคือการวนซ้ำครั้งแรก[11]
เนื่องจากการค้นหาแบบทวิภาคคือขั้นตอนวิธีที่ดีที่สุดในการค้นหาแบบเปรียบเทียบ ปัญหานี้จะถูกลดลงเหลือเพียงการคำนวณความยาวของเส้นทางภายในที่น้อยที่สุดของต้นไม้แบบทวิภาคทั้งหมดที่มีปม ปม ซึ่งจะเท่ากับ:[14]
ตัวอย่างเช่น ในแถวลำดับที่มีสมาชิก 7 ตัว หากค่าเป้าหมายคือราก การค้นหาจะต้องใช้การวนซ้ำหนึ่งครั้ง หากเป็นสมาชิกที่อยู่ล่างรากหนึ่งชั้นจะต้องใช้การวนซ้ำสองครั้ง และสมาชิกสี่ตัวล่างสุดจะต้องใช้การวนซ้ำสามครั้ง ในกรณีนี้ ความยาวของเส้นทางภายในคือ:[14]
จากสมการการคำนวณกรณีเฉลี่ย จำนวนการวนซ้ำโดยเฉลี่ยจะเท่ากับ และผลรวม สามารถเขียนให้อยู่ในรูปอย่างง่ายได้ดังนี้:[11]
แทนค่าสมการ ในสมการ :[11]
สำหรับจำนวนเต็ม สมการด้านบนนี้คือสมการของกรณีเฉลี่ยสำหรับการค้นหาที่สำเร็จ
การค้าหาที่ไม่สำเร็จ
การค้นหาที่ไม่สำเร็จสามารถถูกอธิบายได้โดยการแผ่ขยายต้นไม้ด้วยปมภายนอก (external nodes) ซึ่งจะเกิดเป็นต้นไม้ทวิภาคแบบแผ่ขยาย (extended binary tree) ถ้าปมภายในหรือปมที่ปรากฏในต้นไม้มีปมลูกน้อยกว่า 2 ปม แล้วปมลูกเพิ่มเติมหรือปมภายนอกจะถูกเพิ่มในต้นไม้เพื่อให้ปมภายในแต่ละปมมีปมลูกครบ 2 ปม ด้วยวิธีการนี้แล้วจะทำให้การค้นหาที่ไม่สำเร็จสามารถถูกอธิบายได้ด้วยเส้นทางไปยังปมภายนอกที่มีพ่อแม่เป็นปมเดี่ยวเดียวที่มีอยู่ในการวนซ้ำครั้งสุดท้าย เส้นทางภายนอกคือเส้นทางจากรากสู่ปมภายนอก ซึ่งความยาวของเส้นทางภายนอกนั้นจะเท่ากับผลรวมของความยาวของเส้นทางภายนอกที่เฉพาะ ถ้ามีสมาชิกทั้งหมด ตัว (ซึ่ง จะเป็นจำนวนเต็มบวก) และความยาวของเส้นทางภายนอกคือ แล้วจำนวนการวนซ้ำโดยเฉลี่ยสำหรับการค้นหาที่ไม่สำเร็จคือ โดยจำนวนการวนซ้ำ 1 ครั้งที่ถูกบวกเข้าไปเพิ่มคือการวนซ้ำครั้งแรก สมการความยาวของเส้นทางภายนอกถูกหารด้วย แทนที่จะเป็น เพราะมีเส้นทางภายนอกทั้งหมด เส้น ซึ่งคือช่วงระหว่างและนอกเหนือจากสมาชิกในแถวลำดับ[11]
เช่นเดียวกับการค้นหาที่สำเร็จ ปัญหานี้จะถูกลดลงเหลือเพียงการคำนวณความยาวของเส้นทางภายนอกที่น้อยที่สุดของต้นไม้แบบทวิภาคทั้งหมดที่มีปม ปม สำหรับต้นไม้แบบทวิภาคทั้งหมด ความยาวของเส้นทางภายนอกเท่ากับความยาวของเส้นทางภายในบวกด้วย [14] แทนค่าสมการ :[11]
แทนค่าสมการ ในสมการ สมการของกรณีเฉลี่ยสำหรับการค้นหาที่ไม่สำเร็จคือ:[11]
ประสิทธิภาพของขั้นตอนทางเลือก
ในการวนซ้ำแต่ละครั้งของขั้นตอนการค้นหาแบบทวิภาคด้านบนจะมีการเปรียบเทียบหนึ่งหรือสองครั้ง คือการเปรียบเทียบว่าค่าตรงกลางเท่ากับค่าเป้าหมายหรือไม่ในแต่ละการวนซ้ำ สมมุติให้สมาชิกแต่ละตัวในแถวลำดับมีโอกาสที่จะถูกค้นหาเท่ากัน การวนซ้ำแต่ละครั้งจะมีการเปรียบเทียบทั้งหมด 1.5 ครั้งโดยเฉลี่ย ตัวแปรของขั้นตอนวิธีจะตรวจสอบว่าค่าตรงกลางมีค่าเท่ากับค่าเป้าหมายหรือไม่ในตอนท้ายของการค้นหา ซึ่งทำให้ตัวเปรียบเทียบถูกกำจัดทิ้งไปครึ่งหนึ่งโดยเฉลี่ยในแต่ละการวนซ้ำ สิ่งนี้จะช่วยลดเวลาที่ใช้ในการค้นหาต่อจำนวนการวนซ้ำหนึ่งรอบในคอมพิวเตอร์ส่วนมาก อย่างไรก็ตาม การค้นหานี้จะมีจำนวนการวนซ้ำมากที่สุดอย่างแน่นอน โดยเฉลี่ยแล้วจำนวนการวนซ้ำจะเพิ่มขึ้นหนึ่งครั้ง แต่เนื่องจากการวนเปรียบเทียบจะทำทั้งหมด ครั้งในกรณีที่แย่ที่สุด ประสิทธิภาพที่เพิ่มขึ้นเล็กน้อยในแต่ละการวนซ้ำจึงไม่สามารถทดแทนจำนวนการวนซ้ำที่เพิ่มขึ้นได้ (ยกเว้นในกรณีที่ มีค่ามาก ๆ)[15][16]
ระยะเวลาดำเนินการและแคชที่ใช้ (Running time and cache use)
ในการวิเคราะห์ประสิทธิภาพของการค้นหาแบบทวิภาคจะต้องพิจารณาระยะเวลาที่ใช้ในการเปรียบเทียบสมาชิกสองตัว สำหรับจำนวนเต็มและสตริง (string) ระยะเวลาที่ใช้ในการดำเนินการจะเพิ่มขึ้นแปรผันตรงกับความยาวของการเข้ารหัสสมาชิกหรือก็คือจำนวนบิตของสมาชิก ตัวอย่างเช่น การเปรียบเทียบคู่ของจำนวนเต็มเฉพาะค่าบวกขนาด 64 บิทจะอาศัยการเปรียบเทียบเป็นสองเท่าของการเปรียบเทียบคู่ของจำนวนเต็มเฉพาะค่าบวกขนาด 32 บิท กรณีที่แย่ที่สุดจะเกิดขึ้นเมื่อจำนวนเต็มทั้งสองมีค่าเท่ากัน ซึ่งระยะเวลาดำเนินการนี้จะยิ่งมากอย่างมีนัยสำคัญเมื่อความยาวของการเข้ารหัสสมาชิกมีค่ามาก เช่น การเปรียบเทียบข้อมูลชนิดจำนวนเต็มขนาดใหญ่หรือสตริงแบบยาว ซึ่งจะทำให้การเปรียบเทียบข้อมูลมีราคาแพง นอกจากนั้น การเปรียบเทียบค่าของจำนวนจุดลอยตัว (การแทนจำนวนจริงแบบดิจิทัลที่พบเห็นบ่อยที่สุด) จะแพงกว่าการเปรียบเทียบจำนวนเต็มและสตริงแบบสั้น
ในสถาปัตยกรรมคอมพิวเตอร์ส่วนมาก หน่วยประมวลผลกลางจะมีแคชของฮาร์ดแวร์แยกจากแรม เนื่องจากอยู่ในหน่วยประมวลผลกลาง แคชจะเข้าถึงได้รวดเร็วกว่าแต่ก็กักเก็บข้อมูลได้น้อยกว่าแรม ดังนั้น หน่วยประมวลผลกลางส่วนมากจะกักเก็บตำแหน่งหน่วยความจำ (memory location) ที่ถูกเข้าถึงเมื่อไม่นานมานี้และที่อยู่ใกล้เคียงกัน ยกตัวอย่างเช่น เมื่อเข้าถึงสมาชิกของแถวลำดับ สมาชิกนั้นอาจถูกกักเก็บควบคู่ไปกับสมาชิกที่อยู่ใกล้เคียงกับมันในแรม ทำให้สามารถเข้าถึงสมาชิกที่มีดัชนีใกล้เคียงกัน (locality of reference ) ได้อย่างรวดเร็ว ในแถวลำดับที่มีการเรียงลำดับแล้ว การค้นหาแบบทวิภาคสามารถกระโดดไปยังตำแหน่งหน่วยความจำที่อยู่ไกลได้ถ้าแถวลำดับนั้นมีขนาดใหญ่ ต่างจากขั้นตอนวิธีอื่น เช่น การค้นหาเชิงเส้น และการตรวจสอบเชิงเส้น ในตารางแฮช ซึ่งเข้าถึงสมาชิกได้ตามลำดับเท่านั้น ในระบบส่วนใหญ่ สิ่งนี้อาจเพิ่มระยะเวลาดำเนินการของการค้นหาแบบทวิภาคในแถวลำดับขนาดใหญ่ได้เล็กน้อย[17]
การค้าหาแบบทวิภาคเปรียบเทียบกับการค้นหาแบบอื่น ๆ
การใช้การค้นหาแบบทวิภาคในการดำเนินการเพิ่มและลบสมาชิกในแถวลำดับที่มีการเรียงลำดับไว้แล้วนับเป็นวิธีการที่ไม่มีประสิทธิภาพ เนื่องจากใช้เวลาถึง ในการดำเนินการแต่ละครั้ง นอกจากนั้นแล้ว แถวลำดับที่มีการเรียงลำดับแล้วยังมีการใช้หน่วยความจำที่ซับซ้อน โดยเฉพาะเมื่อสมาชิกถูกเพิ่มเข้าไปในแถวลำดับบ่อย ๆ [18] ดังนั้นจึงมีโครงสร้างข้อมูลอื่น ๆ ที่สามารถดำเนินการเพิ่มและลบได้มีประสิทธิภาพมากกว่า การค้นหาแบบทวิภาคสามารถใช้เพื่อการดำเนินการหาคู่ที่ถูกต้องและการตรวจสอบการเป็นสมาชิกของเซต (ตรวจสอบว่าค่าเป้าหมายอยู่ในกลุ่มสมาชิกข้อมูลหรือไม่) ซึ่งถึงแม้โครงสร้างข้อมูลอื่น ๆ จะสามารถดำเนินการหาคู่ที่ถูกต้องและตรวจสอบการเป็นสมาชิกของเซตได้รวดเร็วกว่าการค้นหาแบบทวิภาค แต่การค้นหาแบบทวิภาคสามารถใช้หาคู่ที่ใกล้เคียงได้อย่างมีประสิทธภาพในขณะที่การค้นหาแบบอื่น ๆ ไม่สามารถทำได้ ซึ่งการค้นหาแบบทวิภาคใช้เวลา โดยไม่คำนึงถึงชนิดของโครงสร้างข้อมูล[19] นอกจากนั้น ยังมีการดำเนินการบางอย่าง เช่น การหาค่าที่มากและน้อยที่สุด ที่สามารถดำเนินการได้อย่างมีประสิทธิภาพในแถวลำดับที่มีการเรียงลำดับแล้ว[8]
การค้นหาเชิงเส้น
การค้นหาเชิงเส้น เป็นขั้นตอนวิธีการค้นหาที่เรียบง่าย โดยจะใช้วิธีการตรวจสอบข้อมูลทุก ๆ ตัวจนกว่าจะเจอค่าเป้าหมาย การค้นหาเชิงเส้นสามารถทำได้ในรายการโยง (linked list) ซึ่งสามารถดำเนินการเพิ่มหรือลบสมาชิกได้รวดเร็วกว่าแถวลำดับ การค้นหาแบบทวิภาคดำเนินการการค้นหาในแถวลำดับได้รวดเร็วกว่าการค้นหาเชิงเส้น (ยกเว้นแถวลำดับที่มีขนาดสั้น) แต่แถวลำดับนั้นจะต้องมีการเรียงลำดับมาก่อน[20] ขั้นตอนวิธีการเรียงลำดับทั้งหมดมีพื้นฐานมาจากการเปรียบเทียบค่าของสมาชิก เช่น ควิกซอร์ต และการเรียงลำดับแบบผสาน ซึ่งใช้การเปรียบเทียบทั้งหมด ในกรณีที่แย่ที่สุด[21] การค้นหาแบบทวิภาคสามารถใช้หาคู่ที่ใกล้เคียงได้อย่างมีประสิทธภาพในขณะที่การค้นหาเชิงเส้นไม่สามารถทำได้ นอกจากนั้น การดำเนินการ เช่น การหาสมาชิกที่มีค่ามากและน้อยที่สุด สามารถทำได้อย่างมีประสิทธิภาพในแถวลำดับที่มีการเรียงลำดับแล้วเท่านั้น[22]
ต้นไม้
ต้นไม้ค้นหาแบบทวิภาค คือโครงสร้างข้อมูลต้นไม้แบบทวิภาคที่มีการดำเนินการโดยอาศัยหลักการของการค้นหาแบบทวิภาค ระเบียนในต้นไม้สามารถถูกค้นหาได้โดยใช้ขั้นตอนวิธีที่คล้ายกับการค้นหาแบบทวิภาค โดยใช้เวลาโดยเฉลี่ยในรูปฟังก์ชันอัลกอริทึม การเพิ่มและลบข้อมูลในต้นไม้ค้นหาแบบทวิภาคก็ใช้เวลาโดยเฉลี่ยในรูปฟังก์ชันอัลกอริทึมเช่นเดียวกัน ซึ่งวิธีนี้จะใช้เวลาน้อยกว่าเวลาในรูปแบบเชิงเส้นที่ใช้ในการเพิ่มหรือลบข้อมูลในแถวลำดับที่มีการเรียงลำดับแล้ว และต้นไม้แบบทวิภาคยังสามารถดำเนินการทุกอย่างได้เหมือนกับที่สามารถทำในแถวลำดับที่มีการเรียงลำดับแล้ว รวมไปถึงการหาขอบเขตและค่าที่ใกล้เคียง[19][23]
อย่างไรก็ตาม ต้นไม้ค้นหาแบบทวิภาคมักจะมีความไม่สมดุลระหว่างสองข้าง ทำให้มีประสิทธิภาพในการค้นหาน้อยกว่าการค้นหาแบบทวิภาคเล็กน้อย สิ่งนี้ยังนำไปใช้ได้กับต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้ หรือคือต้นไม้ค้นหาแบบทวิภาคที่สามารถทำให้ปมของตนเองมีความสมดุลได้ เพราะ ต้นไม้ที่มีจำนวนชั้นน้อยที่สุดเท่าที่จะเป็นไปได้แทบจะไม่ถูกสร้างขึ้นมาเลย นอกเหนือจากต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้แล้ว ต้นไม้มักจะมีความไม่สมดุลอย่างรุนแรงเนื่องจากมีจำนวนปมภายในที่มีปมลูกครบสองปมน้อยมาก ทำให้ระยะเวลาในการค้นหาโดยเฉลี่ยและในกรณีที่แย่ที่สุดใกล้เคียงกับเวลาที่ใช้ในกรณีที่มีการเปรียบเทียบ ครั้ง นอกจากนั้นต้นไม้ค้นหาแบบทวิภาคยังใช้พื้นที่เก็บข้อมูลมากกว่าแถวลำดับที่เรียงลำดับแล้ว[24]
ต้นไม้ค้นหาแบบทวิภาคจะยืมหน่วยความจำภายนอกของฮาร์ดดิสก์เพื่อใช้ในการค้นหาแบบรวดเร็วเนื่องจากต้นไม้ค้นหาแบบทวิภาคสามารถจัดโครงสร้างในระบบแฟ้มข้อมูลได้ ซึ่งต้นไม้แบบบีคือการสรุปวิธีการการจัดระเบียบต้นไม้นี้ โดยต้นไม้แบบบีมักถูกใช้ในการจัดระเบียบพื้นที่จัดเก็บข้อมูลระยะยาว เช่น ฐานข้อมูล และแฟ้มข้อมูล[25][26]
แฮชชิง
โดยปกติแล้วสำหรับการใช้แถวลำดับแบบจับคู่ ตารางแฮช ซึ่งคือโครงสร้างข้อมูลที่เชื่อมโยงคีย์กับระเบียน โดยใช้ฟังก์ชันแฮช จะสามารถนำแถวลำดับแบบจับคู่ไปใช้ได้รวดเร็วกว่าการค้นหาแบบทวิภาคในแถวลำดับระเบียนที่มีการเรียงลำดับแล้ว[27] การใช้ตารางแฮชส่วนมากใช้เวลาโดยเฉลี่ยแบบถัวเฉลี่ย[a][29] อย่างไรก็ตาม แฮชชิงไม่สามารถใช้ในการหาคู่ที่ใกล้เคียง เช่น การคำนวณหาค่าที่น้อยที่สุดตัวถัดไป ค่าที่มากที่สุดตัวถัดไป และคีย์ที่ใกล้เคียงที่สุดได้ เนื่องจากหากการค้นหาไม่สำเร็จจะมีการคืนค่าได้เพียงว่าค่าเป้าหมายนั้นไม่มีอยู่ในระเบียนใด ๆ [30] ดังนั้น การค้นหาแบบทวิภาคจึงถือเป็นวิธีการที่ดีที่สุดสำหรับการหาคู่ประเภทนั้น เนื่องจากใช้เวลาในรูปฟังก์ชันลอการิทึมเท่านั้น นอกจากนั้น การดำเนินการบางอย่าง เช่น การหาสมาชิกที่มีค่ามากหรือน้อยที่สุด สามารถทำได้อย่างมีประสิทธิภาพในแถวลำดับที่มีการเรียงลำดับแล้ว แต่ไม่สามารถทำได้ในตารางแฮช [19]
ขั้นตอนวิธีการตรวจสอบการเป็นสมาชิกของเซต
ปัญหาที่เกี่ยวข้องกับการค้นหาคือ การตรวจสอบการเป็นสมาชิกของเซต ขั้นตอนวิธีที่มีฟังก์ชันการค้นหา เช่น การค้นหาแบบทวิภาค สามารถนำมาใช้ในการตรวจสอบการเป็นสมาชิกของเซตได้ นอกจาการค้นหาแบบทวิภาคแล้วยังมีขั้นตอนวิธีอื่น ๆ ที่เหมาะสมกับการตรวจสอบการเป็นสมาชิกของเซตโดยเฉพาะมากกว่า แถวลำดับบิต คือโครงสร้างข้อมูลที่เรียบง่ายและเป็นประโยชน์ดีสุดเมื่อขอบเขตของคีย์มีจำกัด โดยแถวลำดับบิตจะเก็บข้อมูลโดยใช้พื้นที่น้อยที่สุดในรูปแบบของบิต ซึ่งบิตแต่ละตัวก็จะเป็นตัวแทนของคีย์แต่ละตัวในขอบเขตของคีย์ แถวลำดับบิตมีการดำเนินการที่รวดเร็วมาก โดยใช้เวลาเพียง เท่านั้น [31] นอกจากแถวลำดับบิตแล้ว Judy1 ของแถวลำดับจูดี้ก็ยังสามารถจัดเก็บคีย์ขนาด 64 บิตได้อย่างมีประสิทธิภาพ[32]
สำหรับผลลัพธ์ที่ใกล้เคียง ตัวกรองของบลูม หรือคือโครงสร้างข้อมูลที่เกี่ยวกับความเป็นไปได้ซึ่งอาศัยการแฮชชิง จะกักเก็บเซตของคีย์โดยการเข้ารหัสคีย์ซึ่งจะอาศัยแถวลำดับบิต และฟังก์ชันแฮชหลายฟังก์ชัน ส่วนมากแล้ว ตัวกรองของบลูมจะใช้พื้นที่กักเก็บข้อมูลน้อยกว่าแถวลำดับบิตในขณะที่ก็ใช้เวลาดำเนินการไม่ได้นานกว่า โดยหากอาศัยฟังก์ชันแฮชทั้งหมด ฟังก์ชัน การตรวจสอบการเป็นสมาชิกของเซตจะใช้เวลาดำเนินการเพียง เท่านั้น อย่างไรก็ตาม ตัวกรองของบลูมยังคงมีปัญหาเรื่องผลบวกลวงอยู่ [33]
โครงสร้างข้อมูลอื่น ๆ
ยังมีโครงสร้างข้อมูลอื่น ๆ อีกที่มีการปรับปรุงจากการค้นหาแบบทวิภาคทั้งในด้านการค้นหาและการดำเนินการอื่น ๆ ที่สามารถทำได้ในแถวลำดับที่มีการเรียงลำดับแล้ว ตัวอย่างเช่น โครงสร้างข้อมูลแบบเฉพาะด้าน เช่น Van Emde Boas tree ต้นไม้ฟิวชัน และแถวลำดับบิต สามารถดำเนินการค้นหา การหาคู่ที่ใกล้เคียง และการดำเนินการอื่น ๆ ที่สามารถทำได้ในแถวลำดับที่มีการเรียงลำดับแล้ว ได้อย่างมีประสิทธิภาพมากกว่าการค้นหาแบบทวิภาค โครงสร้างข้อมูลแบบเฉพาะด้านเหล่านี้สามารถดำเนินการได้รวดเร็วกว่า เพราะใช้ประโยชน์จากคุณสมบัติของคีย์ที่มีแอททริบิวต์ (attribute) บางอย่าง (โดยปกติจะเป็นคีย์ที่เป็นจำนวนเต็มที่มีขนาดเล็ก) ดังนั้นสำหรับคีย์ที่ไม่มีแอททริบิวต์เหล่านั้นก็จะทำให้ใช้เวลาและพื้นที่จัดเก็บข้อมูลมากขึ้น[19] ตราบใดที่คีย์นั้นสามารถจัดลำดับได้ การดำเนินการเหล่านี้ก็สามารถดำเนินการได้โดยไม่ต้องคำนึงถึงคีย์ ซึ่งจะมีประสิทธิภาพอย่างต่ำเทียบเท่ากับประสิทธิภาพในแถวลำดับที่มีการเรียงลำดับไว้แล้ว โครงสร้างข้อมูลบางอย่าง เช่น แถวลำดับจูดี้ สามารถใช้วิธีการหลายอย่างร่วมกันเพื่อลดปัญหาที่ได้กล่าวไปในขณะที่ก็ยังคงประสิทธิภาพและความสามารถในการดำเนินการหาคู่ที่ใกล้เคียงไว้อยู่[32]
การค้นหาแบบอื่น ๆ
การค้นหาแบบทวิภาคอย่างมีเอกรูป
การค้นหาแบบทวิภาคอย่างมีเอกรูปจะเก็บค่าผลต่างระหว่างดัชนีของค่ากลางในการวนซ้ำครั้งปัจจุบันและดัชนีของค่ากลางในการวนซ้ำครั้งต่อไป ซึ่งต่างจากการค้นหาแบบทวิภาคที่เก็บค่าดัชนีของขอบเขตบนและล่าง โดยตารางค้นหา ที่เก็บค่าผลต่างนี้จะถูกคำนวณไว้ล่วงหน้า ตัวอย่างเช่น ถ้าแถวลำดับที่กำลังถูกค้นหาคือ [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] แล้วค่ากลาง () คือ 6 ในขณะที่ค่ากลางของแถวลำดับย่อยฝั่งซ้ายหรือ ([1, 2, 3, 4, 5]) คือ 3 และค่ากลางของแถวลำดับย่อยฝั่งขวาหรือ ([7, 8, 9, 10, 11]) คือ 9 การค้นหาแบบทวิภาคอย่างมีเอกรูปจะเก็บค่า 3 เนื่องจากดัชนีค่ากลางตัวต่อไปทั้งสองต่างก็มีผลต่างกับ 6 เท่ากัน[34] เพื่อที่จะลดพื้นที่ที่ใช้ในการค้นหา ขั้นตอนวิธีจะบวกหรือลบผลต่างดังกล่าวจากดัชนีของค่ากลางตัวปัจจุบัน การค้นหาแบบทวิภาคอย่างมีเอกรูปอาจดำเนินการได้รวดเร็วเมื่อถูกใช้ในระบบที่ไม่สามารถคำนวณค่ากลางได้อย่างมีประสิทธิภาพนัก เช่น ในคอมพิวเตอร์แบบทศนิยม [35]
การค้นหาแบบเอกซ์โพเนนเชียล
การค้นหาแบบเอกซ์โพเนนเชียลขยายขอบเขตจากการค้นหาแบบทวิภาคทำให้สามารถดำเนินการได้ในรายการที่ไม่จำกัดขอบเขต โดยจะเริ่มต้นจากการค้นหาสมาชิกตัวแรกที่ดัชนีอยู่ในรูปกำลังของสองและมีค่ามากกว่าค่าเป้าหมาย จากนั้นจึงกำหนดดัชนีของค่านั้นให้เป็นขอบเขตบน และเริ่มดำเนินการค้นหาแบบทวิภาค การค้นหาสมาชิกตัวแรกที่ตรงตามเงื่อนไขจะมีการวนซ้ำทั้งหมด ครั้ง ก่อนที่จะเริ่มการค้นหาแบบทวิภาคซึ่งจะมีการวนซ้ำสูงสุด ครั้ง เมื่อ คือตำแหน่งของค่าเป้าหมาย การค้นหาแบบเอกซ์โพเนนเชียลสามารถทำงานได้ในรายการที่มีการจำกัดขอบเขตเช่นกัน แต่จะมีประสิทธิภาพดีกว่าการค้นหาแบบทวิภาคก็ต่อเมื่อค่าเป้าหมายอยู่ใกล้กับบริเวณเริ่มต้นของแถวลำดับ[36]
การค้นหาโดยการประมาณช่วง
การค้นหาโดยการประมาณช่วงใช้การประมาณตำแหน่งของค่าเป้าหมายโดยพิจารณาจากสมาชิกที่มีค่าสูงสุดและต่ำสุดในแถวลำดับ และขนาดของแถวลำดับ แตกต่างจากการค้นหาแบบก่อนหน้าที่ใช้การคำนวณค่ากลางเป็นหลัก เนื่องจากอาศัยหลักการที่ว่า ค่ากลางมักไม่ใช่การคาดการณ์ที่ดีที่สุดในหลายกรณีที่เป็นไปได้ เช่น ในกรณีที่ค่าเป้าหมายอยู่ใกล้เคียงกับค่าปลายสุดของแถวลำดับ[37]
ฟังก์ชันการประมาณช่วงที่นิยมใช้กัน คือ การประมาณค่าในช่วงเชิงเส้น กำหนดให้ คือแถวลำดับ คือขอบเขตล่างและขอบเขตบนตามลำดับ และ คือค่าเป้าหมาย จะได้ว่าค่าเป้าหมายจะอยู่ห่างจาก และ เป็นระยะประมาณ เมื่อใช้การประมาณค่าในช่วงเชิงเส้นในแถวลำดับที่มีการแจกแจงของสมาชิกแบบเอกรูปหรือใกล้เคียงกับเอกรูป การค้นหาโดยการประมาณช่วงจะทำการเปรียบเทียบทั้งหมด ครั้ง[37][38][39]
ในการทำงานจริง การค้นหาโดยการประมาณช่วงจะดำเนินการช้ากว่าการค้นหาแบบทวิภาคในแถวลำดับที่มีขนาดเล็ก เนื่องจากการค้นหาโดยการประมาณช่วงจะต้องมีการคำนวณเพิ่มเติม แต่เมื่อขนาดแถวลำดับเพิ่มขึ้น อัตราการเพิ่มขึ้นของความซับซ้อนของเวลาในการค้นหาโดยการประมาณช่วงจะช้ากว่าการค้นหาแบบทวิภาค อย่างไรก็ตาม สิ่งนี้สามารถชดเชยได้ในกรณีที่แถวลำดับมีขนาดใหญ่มากเท่านั้น[37]
การเรียงซ้อนแบบเศษส่วน
การเรียงซ้อนแบบเศษส่วน คือเทคนิคที่ใช้ในการเพิ่มความเร็วในการค้นหาแบบทวิภาคสำหรับข้อมูลที่มีค่าเดียวกันในหลายแถวลำดับที่มีการเรียงลำดับแล้ว การค้นหาแยกกันในแต่ละแถวลำดับจะใช้เวลา เมื่อ คือจำนวนแถวลำดับทั้งหมด การเรียงซ้อนแบบเศษส่วนจะลดเวลาการดำเนินการนั้นเหลือเพียง โดยอาศัยการเก็บข้อมูลเกี่ยวกับสมาชิกแต่ละตัวและตำแหน่งของมันในแถวลำดับอื่นลงไปในแถวลำดับแต่ละอัน[40][41]
แต่เดิม การเรียงซ้อนแบบเศษส่วนถูกพัฒนามาเพื่อแก้ปัญหาเกี่ยวกับเรขาคณิตเชิงคำนวณ ได้อย่างมีประสิทธิภาพ ปัจจุบันการเรียงซ้อนแบบเศษส่วนยังถูกนำไปประยุกต์ใช้ในด้านอื่น ๆ อีก เช่น ในการทำเหมืองข้อมูล และในอินเทอร์เน็ตโพรโทคอล[40]
การประยุกต์ใช้ในกราฟ
การค้นหาแบบทวิภาคถูกนำมาใช้กับกราฟบางประเภท โดยค่าเป้าหมายนั้นจะถูกเก็บในรูปของโหนดแทนสมาชิกในแถวลำดับ ต้นไม้ค้นหาแบบทวิภาคคือหนึ่งในตัวอย่างนั้น เมื่อโหนดของต้นไม้ถูกตรวจสอบ ขั้นตอนวิธีจะได้รู้ว่าโหนดนั้นคือเป้าหมายหรือไม่ หรือค่าเป้าหมายจะอยู่ในต้นไม้ย่อยต้นไหน อย่างไรก็ตาม การค้นหาแบบทวิภาคสามารถนำไปใช้ได้ในกราฟอื่นได้อีก เช่น ในกราฟแบบไม่มีทิศทางและถ่วงน้ำหนักเชิงบวก (an undirected, positively weighted graph) ขั้นตอนวิธีจะทราบจากการตรวจสอบโหนดใด ๆ ว่า โหนดนั้นมีค่าเท่ากับค่าเป้าหมายหรือไม่ ถ้าไม่แล้วเส้นเชื่อม (incident edge) ใดที่เป็นเส้นทางที่สั้นที่สุดจากโหนดที่กำลังตรวจสอบอยู่ไปยังโหนดเป้าหมาย เช่นเดียวกัน ต้นไม้ค้นหาแบบทวิภาคจะพิจารณาเส้นเชื่อมไปยังต้นไม้ย่อยฝั่งซ้ายและฝั่งขวาเมื่อโหนดที่กำลังตรวจสอบอยู่มีค่าไม่เท่ากับค่าเป้าหมาย สำหรับกราฟแบบไม่มีทิศทางและถ่วงน้ำหนักเชิงบวกทุกกราฟ ในกรณีที่แย่ที่สุด ขั้นตอนวิธีจะใช้การตรวจสอบทั้งหมด ครั้งจนกว่าจะเจอโหนดเป้าหมาย[42]
Noisy binary search
ขั้นตอนวิธีของ Noisy binary search ถูกใช้แก้ปัญหาในกรณีที่ขั้นตอนวิธีไม่สามารถเปรียบเทียบค่าของสมาชิกในแถวลำดับได้อย่างน่าเชื่อถือ ในการเปรียบเทียบแต่ละคู่สมาชิกนั้นมีโอกาสที่ขั้นตอนวิธีจะเปรียบเทียบได้ผลลัพธ์ที่ไม่ถูกต้อง Noisy binary search สามารถค้นหาตำแหน่งที่ถูกต้องของเป้าหมายได้โดยมีความน่าจะเป็นที่ควบคุมความน่าเชื่อถือของผลลัพธ์ที่ได้ ทุก ๆ Noisy binary search จะต้องมีการเปรียบเทียบอย่างน้อย ครั้งโดยเฉลี่ย โดยที่ คือ binary entropy function และ คือ ความน่าจะเป็นที่กระบวนการนั้นจะคืนค่าตำแหน่งเป้าหมายที่ไม่ถูกต้อง[43][44][45] ปัญหา noisy binary search เช่น เกมของอุลาม [46] คือการถามคำถามยี่สิบข้อ ที่แตกต่างกันเพื่อทายวัตถุหรือตัวเลขนั้น โดยคำตอบที่ได้รับจากคำถามนั้นอาจไม่ถูกต้อง[47]
การค้นหาแบบทวิภาคควอนตัม
การดำเนินการค้นหาแบบทวิภาคในคอมพิวเตอร์แบบดั้งเดิมจะใช้การวนซ้ำทั้งหมด ครั้งในกรณีที่แย่ที่สุด ขั้นตอนวิธีควอนตัม สำหรับการค้นหาแบบทวิภาคจะมีการตรวจสอบทั้งหมด ครั้ง (แทนจำนวนการวนซ้ำในกระบวนการดั้งเดิม) แต่ตัวประกอบคงที่ (constant factor) จะมีค่าน้อยกว่าหนึ่ง ทำให้มีค่าความซับซ้อนของเวลาน้อยลงเมื่อทำงานในคอมพิวเตอร์เชิงควอนตัม กระบวนการของการค้นหาแบบทวิภาคควอนตัมที่แท้จริง หรือคือกระบวนการที่จะคืนค่าผลลัพธ์ที่ถูกต้องเสมอ จะต้องมีการตรวจสอบอย่างน้อย ครั้งในกรณีที่แย่ที่สุด เมื่อ คือ ลอการิทึมธรรมชาติ[48] กระบวนการของการค้นหาแบบทวิภาคควอนตัมที่แท้จริงบางอันดำเนินการตรวจสอบทั้งหมด ครั้งในกรณีที่แย่ที่สุด[49] ในทางตรงกันข้าม ขั้นตอนวิธีของโกรเวอร์ คือขั้นตอนวิธีควอนตัมที่ดีที่สุดสำหรับการค้นหาสมาชิกในรายการแบบไม่มีลำดับ โดยใช้การตรวจสอบทั้งหมด ครั้ง[50]
การใช้ในงานทั่วไป
การค้นหาในข้อมูลที่มีการเรียงลำดับแล้วในงานทั่วไป เช่น พจนานุกรมที่มีการเรียงรายการของคำและความหมาย ถ้ารู้คำเราก็จะสามารถหาความหมายได้, สมุดโทรศัพท์ที่มีการเรียงลำดับรายการชื่อ, ที่อยู่ และเบอร์โทรศัพท์ หากรู้ชื่อก็จะหาเบอร์โทรศัพท์และที่อยู่ได้อย่างรวดเร็ว
ถ้ารายการที่ได้ค้นหามีข้อมูลเล็กน้อยเช่น 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
รายการของคำ
ในการค้นหาทั่วไปมีการใช้การค้นหาแบบทวิภาคและการค้นหาแบบสอดแทรกโดยที่ไม่รู้ตัว เมื่อจะหารายชื่อของบุคคลในสมุดโทรศัพท์ เราต้องเริ่มด้วยการเดาจนเมื่อเรารู้ว่ารายการที่กำลังค้นหานั้นได้มีการเรียงลำดับแล้ว นั่นทำให้เราสามารถค้นหารายชื่อที่ต้องการได้อย่างรวดเร็ว เช่น ถ้าจะหาชื่อ "สมชาย" แต่ถ้าเราเปิดไปเจอหน้าที่มีชื่อ "ศรราม" เราก็จะพลิกไปหน้าถัดๆไปที่เราคะเนไว้ว่าจะมีชื่อที่ต้องการ หากหน้าที่พริกไปนั่นมีชื่อ "องอาจ" ดังนั้นจะสรุปได้ว่ารายชื่อของ "สมชาย" ก็จะอยู่ระหว่างหน้าของ "ศรราม" กับ "องอาจ" ซึ่งขั้นตอนดังกล่าวจะทำให้เราแบ่งปัญหาให้เป็นปัญหาย่อยได้
คลังโปรแกรม
คลังโปรแกรมที่รองรับและพร้อมใช้ในภาษาคอมพิวเตอร์ต่างๆ มีดังต่อไปนี้
ส่วนนี้รอเพิ่มเติมข้อมูล คุณสามารถช่วยเพิ่มข้อมูลส่วนนี้ได้ |
ดูเพิ่ม
เชิงอรรถและอ้างอิง
เชิงอรรถ
อ้างอิง
- ↑ 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" จากแมทเวิลด์.
- ↑ 3.0 3.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.
- ↑ 4.0 4.1 4.2 Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm B".
- ↑ 5.0 5.1 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".
- ↑ 6.0 6.1 Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "History and bibliography".
- ↑ 7.0 7.1 Kasahara & Morishita 2006, pp. 8–9.
- ↑ 8.0 8.1 8.2 Sedgewick & Wayne 2011, §3.1, subsection "Rank and selection".
- ↑ 9.0 9.1 Goldman & Goldman 2008, pp. 461–463.
- ↑ Sedgewick & Wayne 2011, §3.1, subsection "Range queries".
- ↑ 11.00 11.01 11.02 11.03 11.04 11.05 11.06 11.07 11.08 11.09 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.
- ↑ 14.0 14.1 14.2 Knuth 1997, §2.3.4.5 ("Path length").
- ↑ 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").
- ↑ 19.0 19.1 19.2 19.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, §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".
- ↑ 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").
- ↑ 32.0 32.1 Silverstein, Alan, Judy IV shop manual (PDF), Hewlett-Packard, pp. 80–81
- ↑ 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.
- ↑ 37.0 37.1 37.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.
- ↑ 40.0 40.1 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.
บรรณานุกรม
- 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.