![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/8/83/Binary_Search_Depiction.svg/langtr-640px-Binary_Search_Depiction.svg.png&w=640&q=50)
İkili arama algoritması
From Wikipedia, the free encyclopedia
İkili arama (İngilizce: Binary search), sıralı bir dizide, belirli değerin aranmasına yönelik bir algoritmadır. Her adımda, aranan değerin dizinin orta değerine eşit olup olmadığı kontrol edilir. Eşit ise aranan bulunmuştur. Aranan değer orta değerden küçükse, dizinin sıralı olduğu kabulünden, ortanın yukarısına bakmaya gerek kalmaz, arama dizinin başı ve orta değer arasında devam eder. Aranan ortadan büyükse arama orta ile son arasında devam eder. Her adımda dizi ikiye bölünür.
İkili arama algoritması | |
---|---|
![]() İkili aramayla 7 aranırken algoritmanın izlediği yol | |
Sınıf | Arama algoritması |
Veri yapısı | Dizi |
Zaman karmaşıklığı | |
En iyi | |
Ortalama | |
Alan karmaşıklığı |
İkili arama N elemanlı bir dizide en kötü durumda karşılaştırma yapar. Buna göre algoritma, 7 elemanlı veride sonuca 3 adımda ulaşır, 7000000 elemanlı veride, arananın yerinden bağımsız olarak, yalnızca 23 adım gereklidir. Eğer kaba kuvvet yöntemiyle dizinin her elemanı tek tek kontrol edilseydi ve aranan 7000000. indiste bulunsaydı (en kötü durum) 7000000 adım gerekli olacaktı. Bu karşın kaba kuvvet yönteminde dizinin sıralı olma şartı yoktur. Dizinin boyu küçük olduğunda doğrusal arama kullanılabilir.