İkili arama algoritması

İkili Arama, sıralı bir dizide, belirli değerin bulunmasına yönelik bir algoritmadır. Bu teknikteki her bir adımda, aranan değerin, dizinin orta değerine eşit olup olmadığı kontrol edilir. Eşit olmaması durumunda aranan değerin orta değer tarafından ikiye ayrılan kısımlardan hangisinde olduğu kontrol edilir, aranan değeri içeren kısım bir sonraki adımda arama yapılacak dizi olur ve bu sayede arama yapılan listedeki eleman sayısı her adımda yarıya indirilmiş olur.Bu algoritma ile N elemanlı bir dizide en fazla  karşılaştırma yaparak aranan değerin yerini bulmak mümkündür. İkili arama (Binary Search) yöntemi, bir elemanın yerini bulmak için dizinin bütün elemanlarında arama yapan kaba kuvvet arama yönteminden (Ayrıca bkz. Brute-force search) hem zaman hem de bellek açısından daha tasarrufludur.Sıralı bir tam sayı dizisinde, aranan elemanın sırasını döndüren, yoksa -1 döndüren bir Java programı.public static int ara(int[] dizi, int aranan) { // Üzerinde arama yapılacak olan dizi ve aranan sayı.// while bloğu içerisinde bas ve son değişkenleri her adımda değişeceği için burada kontrol ediyoruz. Tek bir eleman kalana kadar döngü devam ediyor.if (aranan < dizi[orta]) { // Aradığımız sayı orta elemandan küçükse, orta elemana ve daha büyüklerine bakmaya gerek yok.} else if (aranan > dizi[orta]) { // Aranan sayı orta elemandan büyükse, orta elemana ve daha küçüklerine bakmaya gerek yok.return orta; // İki if bloğunda da girmiyorsa -küçük ya da büyük değilse- eşit olduğu anlamına geliyor. Sonuç olan bu değeri return ile döndürüyoruz.return -1; // while bloğundan çıkıldıysa, aranan sayı bulunamadı anlamına geliyor. -1 değeri döndürüyoruz.Sıralı bir tam sayı dizisinde, aranan elemanın sırasını döndüren, yoksa -1 döndüren, C++ dilinde yazılmış bir fonksiyon. Örnekte std::vector veri tipi kullanılmıştır. Ancak bu kod, elemanlarına doğrudan erişebildiğiniz ve iterasyon destekleyen her veritipinde kullanılabilir. Örneğin std::dequeile kullanılabilirken, elemanlarına doğrudan erişime izin verilmediği için std::list ve std::set ile kullanılamaz.int ara(std::vector<int> dizi, int aranan){int orta = (bas + son) / 2;         //Her "bas" ve "son" değişkenlerinin değerleri güncelldiğinde kontrol noktamız olan "orta" değişkenini güncelliyoruzson = orta-1;                   //Aradığımız sayı ortadaki sayıdan küçük ise bir sonraki adımda baştan (orta-1)'e kadar olan kısımda arama yapılmalıcontinue;                       //continue değimi döngünğn tamamını kat etmeye gerek kalmadan döngünün başına geri dönmemizi sağlarbas = orta+1;                   //Aradığımız sayı ortadaki sayıdan büyük ise bir sonraki adımda (orta+1)'den sona kadar olan kısımda arama yapılmalıreturn orta;                        //Eğer iki koşula da girmediysek, yani aranan sayı orta sayıdan ne büyük ne de küçük ise, orta sayıyı döndürebilirizreturn -1;                              //Eğer arama sonucunda aranan sayı  bulunamaz ise -1 dönülür.C++'ta ayrıca STL'deki (Standard Template Library) <algorithm> kütüphanesi bir std::binary_search() metodu içerir. Bu metod yukarıdaki örnek kodun aksine sadece iterasyon destekleyen veritiplerinde de kullanılabilir (Örneğin  std::list ve std::set ile  kullanılabilir.). Bu metodun kullanımı şu şekildedir:std::binary_search(iterasyona_başlanan_iterator, iterasyonun_bitiş_iteratoru, aranan_değer) şeklinde kullanılır.std::binary_search() metodu, eğer aranan_değer'i iterasyon yapılan alanda bulabilirse TRUE, bulamaz ize FALSE değeri döner.std::cout << std::boolalpha;    //Programın bool değer bastıracağı zaman 1 yerine true, 0 yerine false bastırması için kullanılan ifade