İkili arama algoritması - Binary search algorithm

İkili arama algoritması

7'nin hedef değer olduğu ikili arama algoritmasının görselleştirilmesi
Sınıf	Arama algoritması
Veri yapısı	Dizi
En kötü durumda verim	Ö(günlük n)
En iyi senaryo verim	Ö(1)
Ortalama verim	Ö(günlük n)
En kötü durumda uzay karmaşıklığı	Ö(1)

İçinde bilgisayar Bilimi, Ikili arama, Ayrıca şöyle bilinir yarım aralıklı arama,^[1] logaritmik arama,^[2] veya ikili pirzola,^[3] bir arama algoritması bir hedef değerin konumunu bir sıralanmış dizi.^[4][5] İkili arama, hedef değeri dizinin orta elemanıyla karşılaştırır. Eşit değillerse, hedefin uzanamayacağı yarı ortadan kaldırılır ve kalan yarıda arama devam eder, yine orta elemanı hedef değer ile karşılaştırmak ve hedef değer bulunana kadar bunu tekrarlamak. Arama kalan yarısı boş olarak biterse, hedef dizide değildir.

İkili arama çalışır logaritmik zaman içinde En kötü durumda, yapımı ${displaystyle O (log n)}$ karşılaştırmalar, nerede ${displaystyle n}$ dizideki öğelerin sayısıdır.^[a][6] İkili arama daha hızlıdır doğrusal arama küçük diziler hariç. Bununla birlikte, ikili aramayı uygulayabilmek için önce dizinin sıralanması gerekir. Uzman var veri yapıları hızlı arama için tasarlanmıştır, örneğin karma tablolar, ikili aramadan daha verimli bir şekilde aranabilir. Bununla birlikte, ikili arama, dizide bulunmasa bile hedefe göre dizideki bir sonraki en küçük veya sonraki en büyük öğeyi bulma gibi daha geniş bir sorun yelpazesini çözmek için kullanılabilir.

İkili aramanın çok sayıda varyasyonu vardır. Özellikle, kesirli basamaklama birden çok dizide aynı değer için ikili aramaları hızlandırır. Kesirli basamaklama, bir dizi arama problemini verimli bir şekilde çözer. hesaplamalı geometri ve diğer birçok alanda. Üstel arama ikili aramayı sınırsız listelere genişletir. ikili arama ağacı ve B ağacı veri yapıları ikili aramaya dayanır.

Algoritma

İkili arama, sıralı diziler üzerinde çalışır. İkili arama, dizinin ortasındaki bir öğeyi hedef değerle karşılaştırarak başlar. Hedef değer öğeyle eşleşirse, dizideki konumu döndürülür. Hedef değer öğeden küçükse, arama dizinin alt yarısında devam eder. Hedef değer öğeden büyükse, arama dizinin üst yarısında devam eder. Bunu yaparak, algoritma hedef değerin her yinelemede bulunamayacağı yarıyı ortadan kaldırır.^[7]

Prosedür

Bir dizi verildiğinde ${displaystyle A}$ nın-nin ${displaystyle n}$ değerleri olan öğeler veya kayıtları ${displaystyle A_ {0}, A_ {1}, A_ {2}, ldots, A_ {n-1}}$öyle sıralandı ${displaystyle A_ {0} leq A_ {1} leq A_ {2} leq cdots leq A_ {n-1}}$ve hedef değer ${displaystyle T}$, aşağıdaki altyordam dizinini bulmak için ikili aramayı kullanır ${displaystyle T}$ içinde ${displaystyle A}$.^[7]

1. Ayarlamak ${displaystyle L}$ -e ${displaystyle 0}$ ve ${displaystyle R}$ -e ${displaystyle n-1}$.
2. Eğer ${görüntü stili L> R}$arama başarısız olarak sona erer.
3. Ayarlamak ${displaystyle m}$ (orta elemanın konumu) zemin nın-nin ${displaystyle {frac {L + R} {2}}}$, bu tamsayı küçüktür veya eşittir ${displaystyle {frac {L + R} {2}}}$.
4. Eğer ${displaystyle A_ {m}$, Ayarlamak ${displaystyle L}$ -e ${displaystyle m + 1}$ ve 2. adıma gidin.
5. Eğer ${displaystyle A_ {m}> T}$, Ayarlamak ${displaystyle R}$ -e ${displaystyle m-1}$ ve 2. adıma gidin.
6. Şimdi ${displaystyle A_ {m} = T}$arama yapıldı; dönüş ${displaystyle m}$.

Bu yinelemeli prosedür, iki değişkenle arama sınırlarının kaydını tutar ${displaystyle L}$ ve ${displaystyle R}$. Prosedür şu şekilde ifade edilebilir: sözde kod aşağıdaki gibi, değişken adları ve türleri yukarıdakiyle aynı kaldığında, zemin zemin işlevi ve başarısız aramanın başarısızlığını ifade eden belirli bir değeri ifade eder.^[7]

işlevi binary_search (A, n, T) dır-dir    L: = 0 R: = n - 1 süre L ≤ R yapmak        m: = kat ((L + R) / 2) Eğer A [m] sonra            L: = m + 1 Aksi takdirde A [m]> T sonra            R: = m - 1 Başka:            dönüş m dönüş başarısız

Alternatif olarak, algoritma, tavan nın-nin ${displaystyle {frac {L + R} {2}}}$. Hedef değer dizide birden fazla görünürse bu, sonucu değiştirebilir.

Alternatif prosedür

Yukarıdaki prosedürde, algoritma ortadaki elemanın (${displaystyle m}$) hedefe eşittir (${displaystyle T}$) her yinelemede. Bazı uygulamalar her yineleme sırasında bu denetimi dışarıda bırakır. Algoritma bu kontrolü yalnızca bir öğe kaldığında gerçekleştirir ( ${displaystyle L = R}$). Bu, yineleme başına bir karşılaştırma ortadan kaldırıldığı için daha hızlı bir karşılaştırma döngüsü sağlar. Ancak, ortalama olarak bir tane daha yineleme gerektirir.^[8]

Hermann Bottenbruch 1962'de bu çeki dışarıda bırakmak için ilk uygulamayı yayınladı.^[8][9]

1. Ayarlamak ${displaystyle L}$ -e ${displaystyle 0}$ ve ${displaystyle R}$ -e ${displaystyle n-1}$.
2. Süre ${displaystyle Leq R}$,
   1. Ayarlamak ${displaystyle m}$ (orta elemanın konumu) tavan nın-nin ${displaystyle {frac {L + R} {2}}}$, bu büyük veya eşit olan en küçük tam sayıdır ${displaystyle {frac {L + R} {2}}}$.
   2. Eğer ${displaystyle A_ {m}> T}$, Ayarlamak ${displaystyle R}$ -e ${displaystyle m-1}$.
   3. Başka, ${displaystyle A_ {m} leq T}$; Ayarlamak ${displaystyle L}$ -e ${displaystyle m}$.
3. Şimdi ${displaystyle L = R}$, arama yapıldı. Eğer ${displaystyle A_ {L} = T}$, dönüş ${displaystyle L}$. Aksi takdirde arama başarısız olarak sona erer.

Nerede tavan tavan işlevi, bu sürüm için sözde kod:

işlevi binary_search_alternative (A, n, T) dır-dir    L: = 0 R: = n - 1 süre L! = R yapmak        m: = tavan ((L + R) / 2) Eğer A [m]> T sonra            R: = m - 1 Başka: U: = m Eğer A [L] = T sonra        dönüş L dönüş başarısız

Yinelenen öğeler

Prosedür, dizide yinelenen öğeler olsa bile öğesi hedef değere eşit olan herhangi bir dizini döndürebilir. Örneğin, aranacak dizi ${displaystyle [1,2,3,4,4,5,6,7]}$ ve hedef oldu ${displaystyle 4}$, bu durumda algoritmanın 4. (dizin 3) veya 5. (dizin 4) öğeyi döndürmesi doğru olur. Normal prosedür, bu durumda 4. öğeyi (dizin 3) döndürür. Her zaman ilk kopyayı döndürmez (dikkate alın ${displaystyle [1,2,4,4,4,5,6,7]}$ hala 4. öğeyi döndürür). Bununla birlikte, bazen dizide yinelenen bir hedef değer için en soldaki veya en sağdaki öğeyi bulmak gerekir. Yukarıdaki örnekte, 4. eleman 4 değerinin en soldaki elemanıdır, 5. eleman ise 4 değerinin en sağındaki elemanıdır. Yukarıdaki alternatif prosedür, eğer böyle bir eleman mevcutsa her zaman en sağdaki elemanın dizinini döndürecektir.^[9]

En soldaki elemanı bulma prosedürü

En soldaki elemanı bulmak için aşağıdaki prosedür kullanılabilir:^[10]

1. Ayarlamak ${displaystyle L}$ -e ${displaystyle 0}$ ve ${displaystyle R}$ -e ${displaystyle n}$.
2. Süre ${displaystyle L$,
   1. Ayarlamak ${displaystyle m}$ (orta elemanın konumu) zemin nın-nin ${displaystyle {frac {L + R} {2}}}$, bu tamsayı küçüktür veya eşittir ${displaystyle {frac {L + R} {2}}}$.
   2. Eğer ${displaystyle A_ {m}$, Ayarlamak ${displaystyle L}$ -e ${displaystyle m + 1}$.
   3. Başka, ${displaystyle A_ {m} geq T}$; Ayarlamak ${displaystyle R}$ -e ${displaystyle m}$.
3. Dönüş ${displaystyle L}$.

Eğer ${displaystyle L$ ve ${displaystyle A_ {L} = T}$, sonra ${displaystyle A_ {L}}$ eşit olan en soldaki öğedir ${displaystyle T}$. Bile ${displaystyle T}$ dizide değil, ${displaystyle L}$ ... sıra nın-nin ${displaystyle T}$ dizide veya dizideki öğelerin sayısı şundan küçüktür: ${displaystyle T}$.

Nerede zemin floor işlevidir, bu sürüm için sözde kod:

işlevi binary_search_leftmost (A, n, T): L: = 0 R: = n süre L Eğer A [m] Başka: R: = m dönüş L

En sağdaki elemanı bulma prosedürü

En sağdaki elemanı bulmak için aşağıdaki prosedür kullanılabilir:^[10]

1. Ayarlamak ${displaystyle L}$ -e ${displaystyle 0}$ ve ${displaystyle R}$ -e ${displaystyle n}$.
2. Süre ${displaystyle L$,
   1. Ayarlamak ${displaystyle m}$ (orta elemanın konumu) zemin nın-nin ${displaystyle {frac {L + R} {2}}}$, bu tamsayı küçüktür veya eşittir ${displaystyle {frac {L + R} {2}}}$.
   2. Eğer ${displaystyle A_ {m}> T}$, Ayarlamak ${displaystyle R}$ -e ${displaystyle m}$.
   3. Başka, ${displaystyle A_ {m} leq T}$; Ayarlamak ${displaystyle L}$ -e ${displaystyle m + 1}$.
3. Dönüş ${displaystyle R-1}$.

Eğer ${görüntü stili L> 0}$ ve ${displaystyle A_ {R-1} = T}$, sonra ${displaystyle A_ {R-1}}$ eşit olan en sağdaki öğedir ${displaystyle T}$. Bile ${displaystyle T}$ dizide değil, ${displaystyle n-R + 1}$ dizide şundan büyük öğelerin sayısıdır ${displaystyle T}$.

Nerede zemin floor işlevidir, bu sürüm için sözde kod:

işlevi binary_search_rightmost (A, n, T): L: = 0 R: = n süre L Eğer Bir [m]> T: R: = m Başka: L: = m + 1 dönüş R - 1

Yaklaşık eşleşmeler

İkili arama, yaklaşık eşleşmeleri hesaplamak için uyarlanabilir. Yukarıdaki örnekte, hedef değer için sıra, öncül, halef ve en yakın komşu gösterilmektedir. ${displaystyle 5}$dizide olmayan.

Yukarıdaki prosedür yalnızca gerçekleştirir tam eşleşir, bir hedef değerin konumunu bulur. Bununla birlikte, ikili arama sıralı diziler üzerinde çalıştığından, yaklaşık eşleşmeleri gerçekleştirmek için ikili aramayı genişletmek önemsizdir. Örneğin, belirli bir değer için, sırasını (daha küçük öğelerin sayısı), öncülünü (sonraki en küçük öğe), halefini (sonraki en büyük öğe) ve hesaplamak için ikili arama kullanılabilir. en yakın komşu. Aralık sorguları iki değer arasındaki eleman sayısının araştırılması, iki sıra sorgusu ile gerçekleştirilebilir.^[11]

• Sıra sorguları, en soldaki elemanı bulma prosedürü. Elementlerin sayısı daha az hedef değer prosedür tarafından döndürülür.^[11]
• Sıra sorguları ile önceki sorgular gerçekleştirilebilir. Hedef değerin sıralaması ${displaystyle r}$selefi${displaystyle r-1}$.^[12]
• Ardıl sorgular için, en sağdaki elemanı bulma prosedürü kullanılabilir. Hedef değer için prosedürü çalıştırmanın sonucu şu ise ${displaystyle r}$, hedef değerin halefi ise${displaystyle r + 1}$.^[12]
• Hedef değerin en yakın komşusu, hangisi daha yakınsa, ya selefi ya da halefidir.
• Aralık sorguları da basittir.^[12] İki değerin sıralaması bilindiğinde, ilk değere eşit veya ondan büyük ve ikinciden küçük öğelerin sayısı, iki sıranın farkıdır. Bu sayı, aralığın uç noktalarının aralığın parçası olarak kabul edilmesi gerekip gerekmediğine ve dizinin bu uç noktalarla eşleşen girişler içerip içermediğine göre bir artırılabilir veya azaltılabilir.^[13]

Verim

Bir ağaç ikili aramayı temsil eder. Burada aranan dizi ${displaystyle [20,30,40,50,80,90,100]}$ve hedef değer ${displaystyle 40}$.

En kötü duruma, arama ağacın en derin seviyesine ulaştığında ulaşılırken, en iyi duruma, hedef değer orta eleman olduğunda ulaşılır.

Karşılaştırma sayısı açısından, ikili aramanın performansı, prosedürün çalışmasını ikili ağaçta görüntüleyerek analiz edilebilir. Ağacın kök düğümü, dizinin orta öğesidir. Alt yarının orta elemanı, kökün sol alt düğümüdür ve üst yarının orta elemanı, kökün sağ alt düğümüdür. Ağacın geri kalanı da benzer şekilde inşa edilmiştir. Kök düğümden başlayarak, sol veya sağ alt ağaçlar, hedef değerin söz konusu düğümden daha az veya daha fazla olmasına bağlı olarak geçilir.^[6][14]

En kötü durumda, ikili arama, ${extstyle lfloor log _ {2} (n) + 1floor}$ karşılaştırma döngüsünün yinelemeleri, burada ${extstyle lfloor floor}$ gösterim, zemin işlevi argümandan küçük veya ona eşit olan en büyük tamsayıyı verir ve ${extstyle günlüğü _ {2}}$ ... ikili logaritma. Bunun nedeni, arama ağacın en derin seviyesine ulaştığında en kötü duruma ulaşılmasıdır ve her zaman ${extstyle lfloor log _ {2} (n) + 1floor}$ herhangi bir ikili arama için ağaçtaki düzeyler.

En kötü duruma, hedef öğe dizide olmadığında da ulaşılabilir. Eğer ${extstyle n}$ ikinin kuvvetinden bir eksikse bu her zaman böyledir. Aksi takdirde arama gerçekleştirilebilir ${extstyle lfloor log _ {2} (n) + 1floor}$arama ağacın en derin seviyesine ulaşırsa yinelemeler. Ancak yapabilir ${extstyle lfloor log _ {2} (n) kat}$ Arama ağacın ikinci en derin seviyesinde biterse, en kötü durumdan bir eksik olan yinelemeler.^[15]

Ortalama olarak, her bir öğenin aranma olasılığının eşit olduğunu varsayarsak, ikili arama ${displaystyle lfloor log _ {2} (n) kat + 1- (2 ^ {lfloor log _ {2} (n) kat +1} -lfloor log _ {2} (n) kat -2) / n}$ hedef öğe dizide olduğunda yinelemeler. Bu yaklaşık olarak eşittir ${displaystyle günlüğü _ {2} (n) -1}$ yinelemeler. Hedef öğe dizide olmadığında, ikili arama ${displaystyle lfloor log _ {2} (n) kat + 2-2 ^ {lfloor log _ {2} (n) kat +1} / (n + 1)}$ Öğeler arasındaki ve dışındaki aralığın eşit derecede aranma olasılığının eşit olduğu varsayılarak, ortalama yinelemeler.^[14]

Hedef değerin dizinin orta öğesi olduğu en iyi durumda, konumu bir yinelemeden sonra döndürülür.^[16]

Yinelemeler açısından, yalnızca öğeleri karşılaştırarak çalışan hiçbir arama algoritması, ikili aramadan daha iyi ortalama ve en kötü durum performansı gösteremez. İkili aramayı temsil eden karşılaştırma ağacı, ağacın en düşük seviyesinin üzerindeki her seviye tamamen doldurulduğu için mümkün olan en az seviyeye sahiptir.^[b] Aksi takdirde, arama algoritması bir yinelemedeki birkaç öğeyi ortadan kaldırarak ortalama ve en kötü durumda gereken yineleme sayısını artırabilir. Karşılaştırmalara dayalı diğer arama algoritmaları için durum budur, çünkü bazı hedef değerler üzerinde daha hızlı çalışabilirken, ortalama performans herşey elemanlar ikili aramadan daha kötüdür. Diziyi ikiye bölerek, ikili arama her iki alt dizinin boyutunun olabildiğince benzer olmasını sağlar.^[14]

Uzay karmaşıklığı

İkili arama, dizinin boyutuna bakılmaksızın, dizi indeksleri veya bellek konumlarına işaretçiler olabilen öğelere üç işaretçi gerektirir. Bu nedenle, ikili aramanın uzay karmaşıklığı ${displaystyle O (1)}$ içinde Kelime RAM hesaplama modeli.

Ortalama vakanın türetilmesi

İkili arama tarafından gerçekleştirilen ortalama yineleme sayısı, aranan her bir öğenin olasılığına bağlıdır. Başarılı aramalar ve başarısız aramalar için ortalama durum farklıdır. Her bir elemanın başarılı aramalar için eşit derecede aranma olasılığının olduğu varsayılacaktır. Başarısız aramalar için, aralıklar Aradaki ve dışındaki elemanların aranması eşit derecede olasıdır. Başarılı aramalar için ortalama durum, her öğeyi tam olarak bir kez aramak için gereken yineleme sayısının şuna bölümüdür: ${displaystyle n}$, elemanların sayısı. Başarısız aramalar için ortalama durum, bir öğeyi her aralıkta tam olarak bir kez aramak için gereken yineleme sayısının, ${displaystyle n + 1}$ aralıklar.^[14]

Başarılı aramalar

İkili ağaç gösteriminde, başarılı bir arama, kökten hedef düğüme giden bir yolla temsil edilebilir; iç yol. Bir yolun uzunluğu, yolun içinden geçtiği kenarların (düğümler arasındaki bağlantıların) sayısıdır. Karşılık gelen yolun uzunluğu olduğu göz önüne alındığında, bir arama tarafından gerçekleştirilen yineleme sayısı ${displaystyle l}$, dır-dir ${displaystyle l + 1}$ ilk yinelemeyi saymak. iç yol uzunluğu tüm benzersiz dahili yolların uzunluklarının toplamıdır. Kökten herhangi bir tek düğüme giden yalnızca bir yol olduğundan, her dahili yol belirli bir öğe için bir aramayı temsil eder. Eğer varsa ${displaystyle n}$ pozitif bir tam sayı olan elemanlar ve dahili yol uzunluğu ${displaystyle I (n)}$, ardından başarılı bir arama için ortalama yineleme sayısı ${displaystyle T (n) = 1 + {frac {I (n)} {n}}}$, ilk yinelemeyi saymak için eklenen bir yineleme ile.^[14]

İkili arama, karşılaştırmalarla arama yapmak için en uygun algoritma olduğundan, bu problem tüm ikili ağaçların minimum dahili yol uzunluğunun hesaplanmasına indirgenmiştir. ${displaystyle n}$ şuna eşit düğümler:^[17]

${displaystyle I (n) = toplam _ {k = 1} ^ {n} sol zemin günlüğü _ {2} (k) ightfloor}$

Örneğin, 7 öğeli bir dizide, kök bir yineleme gerektirir, kökün altındaki iki öğe iki yineleme gerektirir ve aşağıdaki dört öğe üç yineleme gerektirir. Bu durumda, dahili yol uzunluğu:^[17]

${displaystyle toplamı _ {k = 1} ^ {7} leftlfloor log _ {2} (k) ightfloor = 0 + 2 (1) +4 (2) = 2 + 8 = 10}$

Ortalama yineleme sayısı, ${displaystyle 1+ {frac {10} {7}} = 2 {frac {3} {7}}}$ ortalama durum için denkleme dayalı. Toplamı ${displaystyle I (n)}$ basitleştirilebilir:^[14]

${displaystyle I (n) = toplam _ {k = 1} ^ {n} sol kat kütüğü _ {2} (k) ightfloor = (n + 1) sol kat kütüğü _ {2} (n + 1) ightfloor -2 ^ { leftlfloor log _ {2} (n + 1) ightfloor +1} +2}$

Denklemi yerine koyma ${displaystyle I (n)}$ denklemin içine ${görüntü stili T (n)}$:^[14]

${displaystyle T (n) = 1 + {frac {(n + 1) leftlfloor log _ {2} (n + 1) ightfloor -2 ^ {leftlfloor log _ {2} (n + 1) ightfloor +1} +2 } {n}} = lfloor log _ {2} (n) kat + 1- (2 ^ {lfloor log _ {2} (n) kat +1} -lfloor log _ {2} (n) kat -2) / n}$

Tamsayı için ${displaystyle n}$, bu yukarıda belirtilen başarılı bir aramadaki ortalama durum denklemine eşdeğerdir.

Başarısız aramalar

Başarısız aramalar, ağacın büyütülmesiyle temsil edilebilir. harici düğümlerhangi oluşturur genişletilmiş ikili ağaç. Bir iç düğüm veya ağaçta bulunan bir düğüm ikiden az çocuk düğüme sahipse, her bir iç düğümün iki çocuğu olması için harici düğümler olarak adlandırılan ek çocuk düğümler eklenir. Bunu yaparak, başarısız bir arama, ebeveyni son yineleme sırasında kalan tek öğe olan harici bir düğüme giden bir yol olarak temsil edilebilir. Bir dış yol kökten harici bir düğüme giden bir yoldur. dış yol uzunluğu tüm benzersiz harici yolların uzunluklarının toplamıdır. Eğer varsa ${displaystyle n}$ pozitif bir tam sayı olan elemanlar ve harici yol uzunluğu ${displaystyle E (n)}$, ardından başarısız bir arama için ortalama yineleme sayısı ${displaystyle T '(n) = {frac {E (n)} {n + 1}}}$, ilk yinelemeyi saymak için eklenen bir yineleme ile. Dış yol uzunluğu şuna bölünür: ${displaystyle n + 1}$ onun yerine ${displaystyle n}$ Çünkü var ${displaystyle n + 1}$ dizinin öğeleri arasındaki ve dışındaki aralıkları temsil eden harici yollar.^[14]

Bu problem benzer şekilde tüm ikili ağaçların minimum dış yol uzunluğunu belirlemeye indirgenebilir. ${displaystyle n}$ düğümler. Tüm ikili ağaçlar için, dış yol uzunluğu, iç yol uzunluğu artı ${displaystyle 2n}$.^[17] Denklemi yerine koyma ${displaystyle I (n)}$:^[14]

${displaystyle E (n) = I (n) + 2n = sol [(n + 1) sol kat günlüğü _ {2} (n + 1) ightfloor -2 ^ {sol kat günlüğü _ {2} (n + 1) ightfloor + 1} + 2ight] + 2n = (n + 1) (lfloor log _ {2} (n) kat +2) -2 ^ {lfloor log _ {2} (n) kat +1}}$

Denklemi yerine koyma ${displaystyle E (n)}$ denklemin içine ${görüntü stili T '(n)}$başarısız aramalar için ortalama durum belirlenebilir:^[14]

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

Alternatif prosedürün uygulanması

Yukarıda tanımlanan ikili arama prosedürünün her bir yinelemesi, her yinelemede ortadaki öğenin hedefe eşit olup olmadığını kontrol ederek bir veya iki karşılaştırma yapar. Her bir öğenin aranma olasılığının eşit olduğunu varsayarsak, her yineleme ortalama olarak 1,5 karşılaştırma yapar. Algoritmanın bir varyasyonu, aramanın sonunda ortadaki elemanın hedefe eşit olup olmadığını kontrol eder. Ortalama olarak bu, her yinelemeden yarım karşılaştırmayı ortadan kaldırır. Bu, çoğu bilgisayarda yineleme başına harcanan süreyi biraz azaltır. Bununla birlikte, aramaya ortalama bir yineleme ekleyerek, aramanın maksimum sayıda yineleme alacağını garanti eder. Çünkü karşılaştırma döngüsü yalnızca ${extstyle lfloor log _ {2} (n) + 1floor}$ en kötü durumda, yineleme başına verimlilikteki küçük artış, çok büyük hariç tümü için fazladan yinelemeyi telafi etmez ${extstyle n}$.^[c][18][19]

Çalışma süresi ve önbellek kullanımı

İkili aramanın performansını analiz ederken, iki öğeyi karşılaştırmak için gereken zamandır. Tamsayılar ve dizeler için gereken süre, kodlama uzunluğu kadar doğrusal olarak artar (genellikle sayısı bitler ) elemanların sayısı artar. Örneğin, 64 bitlik işaretsiz tamsayı çiftini karşılaştırmak, 32 bitlik işaretsiz tamsayı çiftini karşılaştırırken bitleri ikiye katlamayı gerektirir. En kötü durum, tam sayılar eşit olduğunda elde edilir. Bu, öğelerin kodlama uzunlukları büyük olduğunda önemli olabilir, örneğin büyük tam sayı türleri veya uzun diziler gibi, bu da öğeleri karşılaştırmayı pahalı hale getirir. Ayrıca, karşılaştırma kayan nokta değerler (en yaygın dijital temsili gerçek sayılar ), tam sayıları veya kısa dizeleri karşılaştırmaktan genellikle daha pahalıdır.

Çoğu bilgisayar mimarisinde, işlemci donanımı var önbellek den ayrı Veri deposu. İşlemcinin içinde bulundukları için, önbelleklere erişim çok daha hızlıdır ancak genellikle RAM'den çok daha az veri depolar. Bu nedenle, çoğu işlemci, yakın zamanda erişilen bellek konumlarını, ona yakın bellek konumlarıyla birlikte depolar. Örneğin, bir dizi öğesine erişildiğinde, öğenin kendisi RAM'de kendisine yakın depolanan öğelerle birlikte depolanabilir ve bu da, dizin olarak birbirine yakın olan dizi öğelerine sıralı olarak erişmeyi hızlandırır (referans yeri ). Sıralanmış bir dizide ikili arama, dizi büyükse, algoritmalardan farklı olarak uzak bellek konumlarına atlayabilir (örneğin doğrusal arama ve doğrusal inceleme içinde karma tablolar ) öğelere sırayla erişen. Bu, çoğu sistemde büyük diziler için ikili aramanın çalışma süresine biraz ekler.^[20]

Diğer şemalara karşı ikili arama

İkili aramaya sahip sıralı diziler, ekleme ve silme işlemleri geri alma ile araya eklendiğinde çok verimsiz bir çözümdür. ${extstyle O (n)}$ bu tür her işlem için zaman. Ek olarak, sıralı diziler, özellikle diziye elemanlar sıklıkla eklendiğinde bellek kullanımını karmaşıklaştırabilir.^[21] Çok daha verimli ekleme ve silme işlemini destekleyen başka veri yapıları da vardır. İkili arama, tam eşleme yapmak için kullanılabilir ve üyelik ayarla (bir hedef değerin bir değerler koleksiyonunda olup olmadığını belirleme). Daha hızlı tam eşleştirmeyi ve set üyeliğini destekleyen veri yapıları vardır. Bununla birlikte, diğer birçok arama şemasından farklı olarak, ikili arama, verimli yaklaşık eşleştirme için kullanılabilir, genellikle bu tür eşleşmeleri ${extstyle O (log n)}$ değerlerin türü veya yapısından bağımsız olarak zaman.^[22] Ek olarak, en küçük ve en büyük elemanı bulmak gibi, sıralanmış bir dizide verimli bir şekilde gerçekleştirilebilecek bazı işlemler vardır.^[11]

Doğrusal arama

Doğrusal arama hedef değeri bulana kadar her kaydı kontrol eden basit bir arama algoritmasıdır. Doğrusal arama, bir diziden daha hızlı ekleme ve silme olanağı sağlayan bağlantılı bir listede yapılabilir. Dizinin önceden sıralanması gerekmesine rağmen, dizinin kısa olması dışında ikili arama, sıralı diziler için doğrusal aramadan daha hızlıdır.^[d][24] Herşey sıralama algoritmaları gibi öğeleri karşılaştırmaya dayalı olarak hızlı sıralama ve sıralamayı birleştir, en azından gerekli ${extstyle O (nlog n)}$ en kötü durumda karşılaştırmalar.^[25] Doğrusal aramanın aksine, ikili arama verimli yaklaşık eşleştirme için kullanılabilir. Sıralanmış bir dizide verimli bir şekilde yapılabilen, ancak sıralanmamış bir dizide yapılamayan en küçük ve en büyük elemanı bulma gibi işlemler vardır.^[26]

Ağaçlar

İkili arama ağaçları ikili aramaya benzer bir algoritma kullanılarak aranır.

Bir ikili arama ağacı bir ikili ağaç ikili arama ilkesine göre çalışan veri yapısı. Ağacın kayıtları sıralı bir şekilde düzenlenir ve ağaçtaki her kayıt, ortalama logaritmik süre alınarak ikili aramaya benzer bir algoritma kullanılarak aranabilir. Ekleme ve silme işlemi ayrıca ikili arama ağaçlarında ortalama logaritmik süre gerektirir. Bu, sıralı dizilerin doğrusal zaman eklenmesinden ve silinmesinden daha hızlı olabilir ve ikili ağaçlar, aralık ve yaklaşık sorgular dahil olmak üzere sıralanmış bir dizide olası tüm işlemleri gerçekleştirme yeteneğini korur.^[22][27]

Bununla birlikte, ikili arama genellikle arama için daha etkilidir, çünkü ikili arama ağaçları büyük olasılıkla kusurlu bir şekilde dengelenir ve ikili aramadan biraz daha kötü performansla sonuçlanır. Bu bile geçerlidir dengeli ikili arama ağaçları, mümkün olan en az seviyeyle ağacı nadiren ürettikleri için kendi düğümlerini dengeleyen ikili arama ağaçları. Dengeli ikili arama ağaçları dışında, ağaç, iki çocuklu birkaç dahili düğümle ciddi şekilde dengesiz olabilir ve bu da ortalama ve en kötü durum arama süresinin yaklaşmasına neden olabilir. ${extstyle n}$ karşılaştırmalar.^[e] İkili arama ağaçları, sıralanmış dizilerden daha fazla yer kaplar.^[29]

İkili arama ağaçları, dosya sistemlerinde verimli bir şekilde yapılandırılabildiğinden, ikili arama ağaçları sabit disklerde depolanan harici bellekte hızlı aramaya olanak tanır. B ağacı Bu ağaç düzenleme yöntemini genelleştirir. B-ağaçları genellikle uzun vadeli depolamayı düzenlemek için kullanılır. veritabanları ve dosya sistemleri.^[30][31]

Hashing

Uygulamak için ilişkilendirilebilir diziler, karma tablolar, anahtarları eşleyen bir veri yapısı kayıtları kullanarak Özet fonksiyonu, genellikle sıralanmış bir kayıt dizisinde ikili aramadan daha hızlıdır.^[32] Çoğu karma tablo uygulaması yalnızca itfa edilmiş ortalama sabit süre.^[f][34] Ancak, bir sonraki en küçük, sonraki en büyük ve en yakın anahtarı hesaplamak gibi yaklaşık eşleşmeler için hashing yararlı değildir, çünkü başarısız bir aramada verilen tek bilgi hedefin herhangi bir kayıtta mevcut olmamasıdır.^[35] İkili arama, bu tür eşleşmeler için idealdir ve bunları logaritmik zamanda gerçekleştirir. İkili arama aynı zamanda yaklaşık eşleşmeleri de destekler. En küçük ve en büyük elemanı bulmak gibi bazı işlemler sıralı dizilerde verimli bir şekilde yapılabilir, ancak karma tablolarda yapılamaz.^[22]

Üyelik algoritmalarını ayarlayın

Aramayla ilgili bir sorun şudur: üyelik ayarla. İkili arama gibi arama yapan herhangi bir algoritma set üyeliği için de kullanılabilir. Set üyeliğine daha özel olarak uygun olan başka algoritmalar da vardır. Bir bit dizisi en basit olanıdır, tuş aralığı sınırlı olduğunda kullanışlıdır. Kompakt bir şekilde bir koleksiyon saklar bitler, her bit anahtar aralığı içinde tek bir anahtarı temsil eder. Bit dizileri çok hızlıdır, yalnızca ${extstyle O (1)}$ zaman.^[36] Judy1 türü Judy dizisi 64 bit anahtarları verimli bir şekilde kullanır.^[37]

Yaklaşık sonuçlar için, Bloom filtreleri, hash oluşturmaya dayalı başka bir olasılıklı veri yapısı, Ayarlamak anahtarları bir kullanarak kodlayarak bit dizisi ve çoklu hash fonksiyonları. Bloom filtreleri, çoğu durumda bit dizilerinden çok daha fazla alan verimlidir ve çok daha yavaş değildir: ${extstyle k}$ karma işlevleri, üyelik sorguları yalnızca ${extstyle O (k)}$ zaman. Ancak Bloom filtreleri şunlardan muzdariptir: yanlış pozitifler.^[g][h][39]

Diğer veri yapıları

Sıralanmış diziler için hem arama hem de diğer işlemler için bazı durumlarda ikili aramada gelişebilecek veri yapıları vardır. Örneğin, aramalar, yaklaşık eşleşmeler ve sıralı dizilerde mevcut olan işlemler, özel veri yapıları üzerinde ikili aramadan daha verimli bir şekilde gerçekleştirilebilir. van Emde Boas ağaçları, füzyon ağaçları, dener, ve bit dizileri. Bu özelleştirilmiş veri yapıları genellikle yalnızca daha hızlıdır çünkü belirli bir özniteliğe sahip anahtarların özelliklerinden (genellikle küçük tamsayı olan anahtarlar) yararlanırlar ve bu nedenle bu özniteliğe sahip olmayan anahtarlar için zaman veya alan tüketir.^[22] Anahtarlar sipariş edilebildiği sürece, bu işlemler her zaman en azından verimli bir şekilde, anahtarlardan bağımsız olarak sıralanmış bir dizide yapılabilir. Judy dizileri gibi bazı yapılar, verimliliği ve yaklaşık eşleştirme gerçekleştirme becerisini korurken, bunu azaltmak için bir yaklaşım kombinasyonu kullanır.^[37]

Varyasyonlar

Tek tip ikili arama

Tek tip ikili arama belirli sınırlar yerine mevcut ve sonraki iki olası orta eleman arasındaki farkı depolar.

Tek tip ikili arama, alt ve üst sınırlar yerine, orta elemanın indeksindeki mevcut yinelemeden sonraki yinelemeye kadar olan farkı depolar. Bir arama tablosu farklılıkları içeren önceden hesaplanır. Örneğin, aranacak dizi ise [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]orta eleman (${displaystyle m}$) olabilir 6. Bu durumda, sol alt dizinin orta elemanı ([1, 2, 3, 4, 5]) dır-dir 3 ve sağ alt dizinin orta elemanı ([7, 8, 9, 10, 11]) dır-dir 9. Tek tip ikili arama, 3 her iki endeks de farklı olduğundan 6 aynı miktarda.^[40] Arama alanını azaltmak için, algoritma bu değişikliği orta elemanın indeksine ekler veya çıkarır. Tek tip ikili arama, orta noktayı hesaplamanın verimsiz olduğu sistemlerde daha hızlı olabilir. ondalık bilgisayarlar.^[41]

Üstel arama

Görselleştirme üstel arama sonraki ikili arama için üst sınırı bulma

Üstel arama, ikili aramayı sınırsız listelere genişletir. Hem ikinin üssü olan hem de hedef değerden daha büyük olan bir dizine sahip ilk öğeyi bularak başlar. Daha sonra bu indeksi üst sınır olarak ayarlar ve ikili aramaya geçer. Bir arama ${extstyle lfloor log _ {2} x + 1floor}$ ikili arama başlatılmadan önceki yinelemeler ve en fazla ${extstyle lfloor günlüğü _ {2} xfloor}$ ikili aramanın yinelemeleri, burada ${extstyle x}$ hedef değerin konumudur. Üstel arama, sınırlı listelerde çalışır, ancak yalnızca hedef değer dizinin başlangıcına yakınsa ikili aramaya göre bir gelişme olur.^[42]

İnterpolasyon araması

Görselleştirme enterpolasyon araması doğrusal enterpolasyon kullanarak. Bu durumda, hedefin dizi içindeki konumunun tahmini doğru olduğundan arama yapmaya gerek yoktur. Diğer uygulamalar, hedefin konumunu tahmin etmek için başka bir işlevi belirtebilir.

Orta noktayı hesaplamak yerine, enterpolasyon araması, dizideki en düşük ve en yüksek öğeleri ve ayrıca dizinin uzunluğunu dikkate alarak hedef değerin konumunu tahmin eder. Çoğu durumda orta noktanın en iyi tahmin olmadığı temelinde çalışır. Örneğin, hedef değer dizideki en yüksek öğeye yakınsa, büyük olasılıkla dizinin sonuna yakın bir yerde bulunur.^[43]

Ortak bir enterpolasyon işlevi, doğrusal enterpolasyon. Eğer ${displaystyle A}$ dizi ${displaystyle L, R}$ sırasıyla alt ve üst sınırlardır ve ${displaystyle T}$ hedef ise, hedefin yaklaşık ${displaystyle (T-A_ {L}) / (A_ {R} -A_ {L})}$ yolun ${displaystyle L}$ ve ${displaystyle R}$. Doğrusal enterpolasyon kullanıldığında ve dizi elemanlarının dağılımı tekdüze veya tek tipe yakın olduğunda, enterpolasyon araması yapar ${extstyle O (günlük günlüğü n)}$ karşılaştırmalar.^[43][44][45]

Pratikte, interpolasyon araması ekstra hesaplama gerektirdiğinden, küçük diziler için ikili aramadan daha yavaştır. Zaman karmaşıklığı ikili aramadan daha yavaş büyür, ancak bu yalnızca büyük diziler için ekstra hesaplamayı telafi eder.^[43]

Kesirli basamaklama

İçinde kesirli basamaklama, her dizinin başka bir dizinin her ikinci elemanına işaretçileri vardır, bu nedenle tüm dizileri aramak için yalnızca bir ikili arama yapılması gerekir.

Kesirli basamaklama, birden çok sıralı dizide aynı öğe için ikili aramaları hızlandıran bir tekniktir. Her diziyi ayrı ayrı aramak için ${extstyle O (klog n)}$ zaman, nerede ${extstyle k}$ dizi sayısıdır. Kesirli basamaklama bunu azaltır ${extstyle O (k + log n)}$ her dizide her öğe ve diğer dizilerdeki konumu hakkında belirli bilgileri depolayarak.^[46][47]

Kesirli basamaklama başlangıçta çeşitli sorunları verimli bir şekilde çözmek için geliştirilmiştir. hesaplamalı geometri sorunlar. Kesirli basamaklama, başka yerlerde uygulandı, örneğin veri madenciliği ve internet protokolü yönlendirme.^[46]

Grafiklere genelleme

İkili arama, hedef değerin bir dizi öğesi yerine bir tepe noktasında depolandığı belirli grafik türleri üzerinde çalışmak üzere genelleştirilmiştir. İkili arama ağaçları böyle bir genellemedir - ağaçtaki bir tepe noktası (düğüm) sorgulandığında, algoritma ya tepe noktasının hedef olduğunu ya da hedefin hangi alt ağacın içinde yer alacağını öğrenir. Bununla birlikte, bu daha fazla genelleştirilebilir. aşağıdaki: Yönlendirilmemiş, pozitif ağırlıklı bir grafik ve bir hedef tepe noktası verildiğinde, algoritma bir tepe noktasını sorguladığında hedefe eşit olduğunu öğrenir veya sorgulanan tepe noktasından hedefe en kısa yolda olan bir olay kenarı verilir. Standart ikili arama algoritması, basitçe grafiğin bir yol olduğu durumdur. Benzer şekilde, ikili arama ağaçları, sorgulanan tepe noktası hedefe eşit olmadığında sol veya sağ alt ağaçların kenarlarının verildiği durumdur. Yönlendirilmemiş, pozitif ağırlıklı tüm grafikler için, hedef tepe noktasını bulan bir algoritma vardır. ${displaystyle O (log n)}$ en kötü durumda sorgular.^[48]

Gürültülü ikili arama

Gürültülü ikili aramada, bir karşılaştırmanın yanlış olma olasılığı vardır.

Gürültülü ikili arama algoritmaları, algoritmanın dizinin öğelerini güvenilir bir şekilde karşılaştıramadığı durumu çözer. Her bir öğe çifti için, algoritmanın yanlış karşılaştırma yapması için belirli bir olasılık vardır. Gürültülü ikili arama, verilen konumun güvenilirliğini kontrol eden belirli bir olasılıkla hedefin doğru konumunu bulabilir. Her gürültülü ikili arama prosedürü en azından ${displaystyle (1- au) {frac {log _ {2} (n)} {H (p)}} - {frac {10} {H (p)}}}$ ortalama karşılaştırmalar, nerede ${displaystyle H (p) = - plog _ {2} (p) - (1-p) log _ {2} (1-p)}$ ... ikili entropi işlevi ve ${displaystyle au}$ prosedürün yanlış pozisyon vermesi olasılığıdır.^[49][50][51] Gürültülü ikili arama problemi, bir durum olarak düşünülebilir. Rényi-Ulam oyunu,^[52] bir varyantı Yirmi Soru cevaplar yanlış olabilir.^[53]

Kuantum ikili arama

Klasik bilgisayarlar, tam olarak en kötü durumla sınırlıdır. ${extstyle lfloor log _ {2} n + 1floor}$ ikili arama yaparken yinelemeler. Kuantum algoritmaları ikili arama için hala bir oranla sınırlıdır ${extstyle günlüğü _ {2} n}$ sorgular (klasik prosedürün yinelemelerini temsil eder), ancak sabit faktör birden küçüktür ve daha düşük bir zaman karmaşıklığı sağlar. kuantum bilgisayarlar. Hiç tam kuantum ikili arama prosedürü - yani her zaman doğru sonucu veren bir prosedür - en azından ${extstyle {frac {1} {pi}} (ln n-1) yaklaşık 0.22log _ {2} n}$ en kötü durumda sorgular, nerede ${ extstyle ln }$ ... doğal logaritma.^[54] There is an exact quantum binary search procedure that runs in ${ extstyle 4log _{605}napprox 0.433log _{2}n}$ queries in the worst case.^[55] Karşılaştırıldığında, Grover algoritması is the optimal quantum algorithm for searching an unordered list of elements, and it requires ${displaystyle O({sqrt {n}})}$ sorguları.^[56]

Tarih

The idea of sorting a list of items to allow for faster searching dates back to antiquity. The earliest known example was the Inakibit-Anu tablet from Babylon dating back to c. MÖ 200. The tablet contained about 500 Altmışlık numbers and their karşılıklılar sorted in Sözlük düzeni, which made searching for a specific entry easier. In addition, several lists of names that were sorted by their first letter were discovered on the Ege adaları. Katolikon, a Latin dictionary finished in 1286 CE, was the first work to describe rules for sorting words into alphabetical order, as opposed to just the first few letters.^[9]

1946'da, John Mauchly made the first mention of binary search as part of the Moore Okul Dersleri, a seminal and foundational college course in computing.^[9] 1957'de William Wesley Peterson published the first method for interpolation search.^[9][57] Every published binary search algorithm worked only for arrays whose length is one less than a power of two^[ben] until 1960, when Derrick Henry Lehmer published a binary search algorithm that worked on all arrays.^[59] In 1962, Hermann Bottenbruch presented an ALGOL 60 implementation of binary search that placed the comparison for equality at the end, increasing the average number of iterations by one, but reducing to one the number of comparisons per iteration.^[8] uniform binary search was developed by A. K. Chandra of Stanford Üniversitesi 1971'de.^[9] 1986'da Bernard Chazelle ve Leonidas J. Guibas tanıtıldı fractional cascading as a method to solve numerous search problems in hesaplamalı geometri.^[46][60][61]

Uygulama sorunları

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky

— Donald Knuth^[2]

Ne zaman Jon Bentley assigned binary search as a problem in a course for professional programmers, he found that ninety percent failed to provide a correct solution after several hours of working on it, mainly because the incorrect implementations failed to run or returned a wrong answer in rare uç durumlarda.^[62] A study published in 1988 shows that accurate code for it is only found in five out of twenty textbooks.^[63] Furthermore, Bentley's own implementation of binary search, published in his 1986 book İncileri Programlama, contained an overflow error that remained undetected for over twenty years. Java programlama dili library implementation of binary search had the same overflow bug for more than nine years.^[64]

In a practical implementation, the variables used to represent the indices will often be of fixed size, and this can result in an aritmetik taşma for very large arrays. If the midpoint of the span is calculated as ${displaystyle {frac {L+R}{2}}}$, then the value of ${displaystyle L+R}$ may exceed the range of integers of the data type used to store the midpoint, even if ${displaystyle L}$ ve ${displaystyle R}$ are within the range. Eğer ${displaystyle L}$ ve ${displaystyle R}$ are nonnegative, this can be avoided by calculating the midpoint as ${displaystyle L+{frac {R-L}{2}}}$.^[65]

An infinite loop may occur if the exit conditions for the loop are not defined correctly. bir Zamanlar ${displaystyle L}$ aşıyor ${displaystyle R}$, the search has failed and must convey the failure of the search. In addition, the loop must be exited when the target element is found, or in the case of an implementation where this check is moved to the end, checks for whether the search was successful or failed at the end must be in place. Bentley found that most of the programmers who incorrectly implemented binary search made an error in defining the exit conditions.^[8][66]

Library support

Many languages' standart kitaplıklar include binary search routines:

• C sağlar işlevi bsearch() onun içinde standart kitaplık, which is typically implemented via binary search, although the official standard does not require it so.^[67]
• C ++ 's Standart Şablon Kitaplığı provides the functions binary_search(), lower_bound(), upper_bound() ve equal_range().^[68]
• D 's standard library Phobos, in std.range module provides a type SortedRange (returned by sort() ve assumeSorted() functions) with methods içerir (), equaleRange(), lowerBound() ve trisect(), that use binary search techniques by default for ranges that offer random access.^[69]
• COBOL sağlar SEARCH ALL verb for performing binary searches on COBOL ordered tables.^[70]
• Git 's çeşit standard library package contains the functions Arama, SearchInts, SearchFloat64s, ve SearchStrings, which implement general binary search, as well as specific implementations for searching slices of integers, floating-point numbers, and strings, respectively.^[71]
• Java offers a set of aşırı yüklenmiş binarySearch() static methods in the classes Diziler ve Koleksiyonlar standartta java.util package for performing binary searches on Java arrays and on Listes, respectively.^[72][73]
• Microsoft 's .NET Framework 2.0 offers static genel versions of the binary search algorithm in its collection base classes. Bir örnek olabilir System.Array's method BinarySearch(T[] array, T value).^[74]
• İçin Amaç-C, Kakao framework provides the NSArray -indexOfObject:inSortedRange:options:usingComparator: method in Mac OS X 10.6+.^[75] Elmalar Çekirdek Vakfı C framework also contains a CFArrayBSearchValues() işlevi.^[76]
• Python sağlar bisect modül.^[77]
• Yakut 's Array class includes a bsearch method with built-in approximate matching.^[78]

Ayrıca bakınız

• Bisection method – Algorithm for finding a zero of a function – the same idea used to solve equations in the real numbers
• Multiplicative binary search – Binary search variation with simplified midpoint calculation

Notlar ve referanslar

Bu makale şu adrese gönderildi WikiJournal of Science harici için akademik akran değerlendirmesi in 2018 (gözden geçiren raporları ). Güncellenen içerik, Wikipedia sayfasına bir CC-BY-SA-3.0 lisans (2019 ). Kaydın incelenen versiyonu: Anthony Lin; et al. (2 July 2019), "Binary search algorithm" (PDF), WikiJournal of Science, 2 (1): 5, doi:10.15347/WJS/2019.005, ISSN  2470-6345, Vikiveri  Q81434400

Notlar

Alıntılar

Kaynaklar

Dış bağlantılar

• NIST Dictionary of Algorithms and Data Structures: binary search
• Comparisons and benchmarks of a variety of binary search implementations in C