Tanım
İ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 (Ayrıca bkz. Brute-force search) hem zaman hem de bellek açısından daha tasarrufludur.
Örnekler
Sıralı bir tam sayı dizisinde, aranan elemanın sırasını döndüren, yoksa -1 döndüren bir Java programı.
public class IkiliArama { // Java programının çalışması için gerekli olan public class. public static int ara(int[] dizi, int aranan) { // Üzerinde arama yapılacak olan dizi ve aranan sayı. int bas = 0; // Dizinin en başındaki elemanın sırası. int son = dizi.length - 1; // Dizinin en sonundaki elemanın sırası. // 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. while (bas <= son) { int orta = (bas + son) / 2; if (aranan < dizi[orta]) { // Aradığımız sayı orta elemandan küçükse, orta elemana ve daha büyüklerine bakmaya gerek yok. son = orta - 1; // Artık dizinin son elemanı, orta'nın bir eksiği. } else if (aranan > dizi[orta]) { // Aranan sayı orta elemandan büyükse, orta elemana ve daha küçüklerine bakmaya gerek yok. bas = orta + 1; // Artık dizinin baş elemanı, orta'nın bir fazlası. } else { 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::deque
ile 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 bas = 0; //Aramaya başlanacak index int son = dizi.size() - 1; //Aramacak son index while (bas<=son){ 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üncelliyoruz if (aranan < dizi[orta]) { son = 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ğlar } else if(aranan > dizi[orta]){ bas = 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ı continue; } 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ürebiliriz } return -1; //Eğer arama sonucunda aranan sayı bulunamaz ise -1 dönülür. }
binary_search() metodu
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:
#include <algorithm>
ile <algorithm> kütüphanesi ana koda dahil edilir.std::binary_search(iterasyona_başlanan_, iterasyonun_bitiş_iteratoru, aranan_değer)
şeklinde kullanılır.std::binary_search()
metodu, eğeraranan_değer
'i iterasyon yapılan alanda bulabilirseTRUE
, bulamaz izeFALSE
değeri döner.
#include <iostream> #include <vector> #include <algorithm> int main(){ 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 int aranan_sayi = 11; std::vector<int> sayilar{ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15); //Sıralı dizimiz bool t_f = std::binary_search(sayilar.begin(), sayilar.end(), aranan_sayi); //binary_search() std::cout << "Dizide aranan değer: " << aranan_sayi << "\nSonuç: " << t_f << std::endl; return 0; }
Kaynakça
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
TanimIkili Arama sirali bir dizide belirli degerin bulunmasina yonelik bir algoritmadir Bu teknikteki her bir adimda aranan degerin dizinin orta degerine esit olup olmadigi kontrol edilir Esit olmamasi durumunda aranan degerin orta deger tarafindan ikiye ayrilan kisimlardan hangisinde oldugu kontrol edilir aranan degeri iceren kisim bir sonraki adimda arama yapilacak dizi olur ve bu sayede arama yapilan listedeki eleman sayisi her adimda yariya indirilmis olur Bu algoritma ile N elemanli bir dizide en fazla log2 N displaystyle lceil log 2 N rceil karsilastirma yaparak aranan degerin yerini bulmak mumkundur Ikili arama Binary Search yontemi bir elemanin yerini bulmak icin dizinin butun elemanlarinda arama yapan Ayrica bkz Brute force search hem zaman hem de bellek acisindan daha tasarrufludur OrneklerJava Sirali bir tam sayi dizisinde aranan elemanin sirasini donduren yoksa 1 donduren bir Java programi public class IkiliArama Java programinin calismasi icin gerekli olan public class public static int ara int dizi int aranan Uzerinde arama yapilacak olan dizi ve aranan sayi int bas 0 Dizinin en basindaki elemanin sirasi int son dizi length 1 Dizinin en sonundaki elemanin sirasi while blogu icerisinde bas ve son degiskenleri her adimda degisecegi icin burada kontrol ediyoruz Tek bir eleman kalana kadar dongu devam ediyor while bas lt son int orta bas son 2 if aranan lt dizi orta Aradigimiz sayi orta elemandan kucukse orta elemana ve daha buyuklerine bakmaya gerek yok son orta 1 Artik dizinin son elemani orta nin bir eksigi else if aranan gt dizi orta Aranan sayi orta elemandan buyukse orta elemana ve daha kucuklerine bakmaya gerek yok bas orta 1 Artik dizinin bas elemani orta nin bir fazlasi else return orta Iki if blogunda da girmiyorsa kucuk ya da buyuk degilse esit oldugu anlamina geliyor Sonuc olan bu degeri return ile donduruyoruz return 1 while blogundan cikildiysa aranan sayi bulunamadi anlamina geliyor 1 degeri donduruyoruz C Sirali bir tam sayi dizisinde aranan elemanin sirasini donduren yoksa 1 donduren C dilinde yazilmis bir fonksiyon Ornekte std vector veri tipi kullanilmistir Ancak bu kod elemanlarina dogrudan erisebildiginiz ve iterasyon destekleyen her veritipinde kullanilabilir Ornegin std dequeile kullanilabilirken elemanlarina dogrudan erisime izin verilmedigi icin std list ve std set ile kullanilamaz int ara std vector lt int gt dizi int aranan int bas 0 Aramaya baslanacak index int son dizi size 1 Aramacak son index while bas lt son int orta bas son 2 Her bas ve son degiskenlerinin degerleri guncelldiginde kontrol noktamiz olan orta degiskenini guncelliyoruz if aranan lt dizi orta son orta 1 Aradigimiz sayi ortadaki sayidan kucuk ise bir sonraki adimda bastan orta 1 e kadar olan kisimda arama yapilmali continue continue degimi dongungn tamamini kat etmeye gerek kalmadan dongunun basina geri donmemizi saglar else if aranan gt dizi orta bas orta 1 Aradigimiz sayi ortadaki sayidan buyuk ise bir sonraki adimda orta 1 den sona kadar olan kisimda arama yapilmali continue return orta Eger iki kosula da girmediysek yani aranan sayi orta sayidan ne buyuk ne de kucuk ise orta sayiyi dondurebiliriz return 1 Eger arama sonucunda aranan sayi bulunamaz ise 1 donulur binary search metodu C ta ayrica STL deki Standard Template Library lt algorithm gt kutuphanesi bir std binary search metodu icerir Bu metod yukaridaki ornek kodun aksine sadece iterasyon destekleyen veritiplerinde de kullanilabilir Ornegin std list ve std set ile kullanilabilir Bu metodun kullanimi su sekildedir include lt algorithm gt ile lt algorithm gt kutuphanesi ana koda dahil edilir std binary search iterasyona baslanan iterasyonun bitis iteratoru aranan deger seklinde kullanilir std binary search metodu eger aranan deger i iterasyon yapilan alanda bulabilirse TRUE bulamaz ize FALSE degeri doner include lt iostream gt include lt vector gt include lt algorithm gt int main std cout lt lt std boolalpha Programin bool deger bastiracagi zaman 1 yerine true 0 yerine false bastirmasi icin kullanilan ifade int aranan sayi 11 std vector lt int gt sayilar 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Sirali dizimiz bool t f std binary search sayilar begin sayilar end aranan sayi binary search std cout lt lt Dizide aranan deger lt lt aranan sayi lt lt n Sonuc lt lt t f lt lt std endl return 0 Kaynakca en cppreference com 26 Haziran 2011 tarihinde kaynagindan arsivlendi Erisim tarihi 4 Temmuz 2021 en cppreference com 29 Haziran 2011 tarihinde kaynagindan arsivlendi Erisim tarihi 4 Temmuz 2021