Binary search, sıralı bir listede hedef değeri bulmak için her adımda ortadaki elemanı kontrol eden ve hedefin bulunamayacağı yarıyı arama alanından çıkaran bir arama yöntemidir. Bu yaklaşım, elemanları baştan sona inceleyen doğrusal aramadan farklı olarak aramayı adım adım daraltır.
Ancak binary search yalnızca listenin küçükten büyüğe veya büyükten küçüğe tutarlı biçimde sıralandığı durumlarda güvenilir çalışır. Liste sıralı değilse, ortadaki değerle karşılaştırma yaparak hedefin sol tarafta mı yoksa sağ tarafta mı olduğunu kesin biçimde anlayamazsınız.
Binary Search Nedir ve Neden Arama Alanını Yarıya İndirir?
Doğrusal aramada listenin ilk elemanından başlanır ve hedef bulunana kadar elemanlar sırayla kontrol edilir. Örneğin hedef değer listenin sonlarına yakınsa, önceki birçok elemanın incelenmesi gerekir. Bu yöntem küçük veya sırasız listelerde anlaşılır ve kullanışlı olabilir.
Binary search ise listenin ortasındaki değeri seçer. Ortadaki değer hedefe eşitse arama tamamlanır. Hedef, ortadaki değerden büyükse listenin sol yarısı; küçükse sağ yarısı artık dikkate alınmaz. Böylece her turda arama yapılabilecek alan yaklaşık yarıya düşer.
Örneğin küçükten büyüğe sıralanmış bir listede ortadaki değer 40, hedef ise 65 olsun. 65 sayısının 40’tan büyük olduğunu bildiğimiz için 40’ın solunda kalan değerleri yeniden incelemeye gerek yoktur. Çünkü sıralama kuralı gereği o bölümdeki değerler 40’tan daha küçük veya ona eşittir. Arama doğrudan sağ yarıda sürdürülür.
Bu yöntemin temel avantajı, liste büyüdükçe kontrol edilen alanın katmanlar hâlinde küçülmesidir. Bu davranış genellikle O(log n) ifadesiyle anlatılır. Buradaki fikir, her adımda tüm listeyi dolaşmak yerine kalan arama alanını bölerek daha küçük bir bölüm üzerinde çalışmaktır. Bu ifade binary search’ün her durumda en hızlı yöntem olduğu anlamına gelmez; yöntemin kullanılabilmesi için sıralama koşulu ve uygun veri yapısı bulunmalıdır.
Low, Mid ve High Sınırları Adım Adım Nasıl Güncellenir?
Binary search sırasında arama alanını üç dizinle takip ederiz: low ilk geçerli dizini, high son geçerli dizini, mid ise low ile high arasındaki orta dizini gösterir.
Şu sıralı listeyi ve 31 hedefini kullanalım:
[3, 8, 12, 17, 23, 31, 42, 56, 71]
Listenin dizinleri 0’dan 8’e kadardır. İlk turda low = 0 ve high = 8 olur. Bu iki sınır arasındaki orta dizin mid = 4’tür. Dördüncü dizindeki değer 23’tür. Hedef olan 31, 23’ten büyük olduğu için 0–4 aralığı elenir ve yeni low değeri mid + 1, yani 5 olur.
| Tur | low | mid | high | Listedeki mid değeri | Karar |
|---|---|---|---|---|---|
| 1 | 0 | 4 | 8 | 23 | 31 daha büyük, low = 5 |
| 2 | 5 | 6 | 8 | 42 | 31 daha küçük, high = 5 |
| 3 | 5 | 5 | 5 | 31 | Hedef bulundu |
İkinci turda hedef 31, ortadaki 42 değerinden küçük olduğu için sağ taraf elenir. Bu kez high = mid - 1 uygulanır ve high değeri 5 olur. Son turda low, mid ve high aynı dizini gösterir. Listedeki bu dizinin değeri 31 olduğu için arama sona erer.
Burada low, mid ve high değerleri dizinleri gösterir; listedeki gerçek sayıları değil. Örneğin mid = 5 ifadesi, “hedef 5” anlamına gelmez. Yalnızca listenin 5 numaralı konumundaki değerin kontrol edildiğini belirtir.
Python ile Döngü Tabanlı Binary Search Uygulaması
Aşağıdaki döngü tabanlı binary_search fonksiyonu, sıralı bir liste ile hedef değeri alır. Hedef bulunursa listedeki dizinini, bulunamazsa -1 değerini döndürür.
def binary_search(numbers, target):
low, high = 0, len(numbers) - 1
while low <= high:
mid = (low + high) // 2
if numbers[mid] == target:
return mid
if numbers[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
numbers = [10, 15, 20, 25, 28, 31, 40]
print(binary_search(numbers, 31))
print(binary_search(numbers, 30))Bu kodun beklenen çıktısı şöyledir:
5
-1- low: Aramanın başlayabileceği en düşük dizini gösterir.
- high: Aramanın devam edebileceği en yüksek dizini gösterir.
- mid: low ve high arasındaki orta dizindir. Karşılaştırma bu konumdaki değer üzerinden yapılır.
Binary search, yalnızca sıralı listelerde doğrudan güvenilir biçimde uygulanabilir. Algoritma, mid konumundaki değere bakarak hedefin sol yarıda mı, sağ yarıda mı bulunacağına sıralama sayesinde karar verir. Liste sıralanmamışsa bu karar yanlış dala yöneltebilir; hedef listede bulunsa bile hatalı biçimde bulunamayabilir.
Bulunamayan Değer ve Sınır Durumları Nasıl Yönetilir?
Hedef listede yoksa arama, her adımda olası alanı daraltır ve sonunda low > high olur. Bu koşul, kontrol edilecek geçerli bir aralık kalmadığını gösterir. Böyle bir durumda -1 döndürmek, çağıran kodun “değer bulunamadı” sonucunu açıkça ayırt etmesini sağlar. Temel algoritma kavramlarını algoritma bilgi testi ile kontrol etmek, bu sınır mantığını pekiştirmeye yardımcı olabilir.
- Tek elemanlı liste: Liste
[31]ise hedef 31 olduğunda orta konum 0 seçilir ve sonuç 0 olur. Hedef 30 ise değer karşılaştırılır, aralık daralır ve sonuç -1 döner. - Boş liste: Listenin uzunluğu 0 olduğunda
high = -1olur. Başlangıçtalow > higholduğu için döngüye girilmeden -1 döndürülür. - Çift elemanlı liste:
[20, 31]gibi iki elemanlı bir listede tam bir orta konum yoktur. Tamsayı bölmesi orta konumlardan birini seçer. Hedefe görelowveyahighdoğru biçimde güncellenirse arama ilerler. - İlk eleman: Hedef ilk değerse karşılaştırmalar sonunda
highküçülür ve ilk dizin kontrol edilir. - Son eleman: Hedef son değerse
lowyükseltilir ve son dizin arama aralığında kalır.
| Özellik | Doğrusal arama | Binary search |
|---|---|---|
| Veri sıralı olmalı mı? | Hayır | Evet |
| Arama yöntemi | Elemanları sırayla kontrol eder | Arama alanını iki parçaya ayırır |
| Uygulama mantığı | Daha basit ve doğrudandır | low, mid ve high sınırlarını yönetir |
| Uygun kullanım | Sırasız veya küçük listeler | Sıralı ve tekrar tekrar aranacak listeler |
Binary Search Gerçek Hayatta Nerede İşe Yarar?
Binary search, arama alanının önceden sıralı olduğu ve her karşılaştırmada hangi yarının elenebileceğinin anlaşılabildiği durumlarda işe yarar. Örneğin sözlükte bir kelimeyi ararken sayfaları tek tek baştan okumak yerine yaklaşık orta bölüme bakar, kelimenin alfabetik olarak önce mi sonra mı geldiğine göre arama alanını daraltırsınız. Algoritmanın temel mantığı da buna dayanır.
Bu tür problemleri değerlendirirken yalnızca algoritmayı değil, genel kodlama temelinizi de gözden geçirmek faydalı olabilir. Özellikle karşılaştırma, döngü ve koşul mantığını birlikte kullanmanız gereken durumlarda ücretsiz yazılım bilgisi testi seviyenizi fark etmenize yardımcı olabilir.
Sıralı sözlükte kelime arama
Basılı bir sözlükte kelimeler alfabetik sıradadır. “programlama” kelimesini ararken sözlüğün ortasındaki kelimeye bakıp hedef kelimenin alfabetik olarak önce veya sonra geldiğini belirlersiniz. Böylece arama yapılacak sayfaların bir bölümü elenir. Aynı yaklaşım, kelimelerin alfabetik sırada tutulduğu bir yazılım sisteminde de uygulanabilir.
Alfabetik telefon rehberinde kayıt bulma
Telefon rehberindeki kişiler soyadına veya adına göre alfabetik biçimde sıralanmışsa belirli bir kişiyi aramak için binary search mantığı kullanılabilir. Orta noktadaki kayıt hedef kişiden alfabetik olarak önceyse arama alanı sonraki kayıtlara taşınır; sonra ise önceki kayıtlara dönülür.
Burada önemli ayrıntı, yalnızca kayıtların “bir şekilde düzenli görünmesi” değildir. Sıralama ölçütü açık ve tutarlı olmalıdır. Rehber bazı yerlerde ada, bazı yerlerde soyada göre sıralanmışsa ya da büyük-küçük harf ve karakter karşılaştırmaları farklı uygulanıyorsa orta değere bakarak güvenilir bir karar vermek zorlaşır.
Tarih, numara veya ada göre sıralanmış kayıtlar
Bir etkinlik listesindeki kayıtlar tarihe göre sıralıysa belirli bir tarihe ait kayıtları aramak için binary search kullanılabilir. Benzer şekilde öğrenci numaraları artan sırada, ürün kodları düzenli biçimde veya müşteri adları alfabetik sırada tutuluyorsa hedef değerin hangi tarafta aranacağı belirlenebilir.
Ancak verilerin sürekli eklendiği, silindiği veya güncellendiği sistemlerde karar yalnızca arama algoritmasına göre verilmez. Öncelikle şu noktalar değerlendirilmelidir:
- Veriyi sıralı tutmak için her ekleme ve silme işleminde ek çalışma gerekiyor mu?
- Aramalar sık mı yapılacak, yoksa yalnızca ara sıra tek bir kayıt mı aranacak?
- Veri yapısı, sıralı erişimi ve güncellemeleri destekliyor mu?
- Arama için kullanılacak karşılaştırma ölçütü kesin olarak tanımlanmış mı?
Bu nedenle gerçek hayattaki doğru soru “Binary search her yerde kullanılabilir mi?” değil, “Veriyi bu algoritmanın karar verebileceği biçimde düzenlemek mantıklı mı?” sorusudur.
Binary Search Kullanmalı mıyım? Kısa Karar Kontrol Listesi
Bir arama probleminde aşağıdaki sorulara cevap vererek binary search için uygun koşulların oluşup oluşmadığını hızlıca değerlendirebilirsiniz:
- Liste veya arama alanı sıralı mı?
- Sıralama düzeni baştan sona tutarlı mı?
- Hedef değer ile ortadaki değer aynı ölçüte göre karşılaştırılabiliyor mu?
- Karşılaştırma sonucunda arama alanının hangi yarısının eleneceği güvenilir biçimde belirlenebiliyor mu?
- Veriyi sıralı tutmanın veya aramadan önce sıralamanın oluşturacağı ek işlem kabul edilebilir mi?
- Arama işlemi tekrar tekrar yapılacak mı?
- Veri güncellendiğinde sıralı düzen korunabilecek mi?
Liste sıralı değilse ve yalnızca küçük bir veri kümesinde tek seferlik arama yapılacaksa doğrusal arama daha anlaşılır bir seçenek olabilir. Bu yaklaşımda elemanlar sırayla kontrol edilir ve hedef bulunduğunda işlem sonlandırılır. Buna karşılık aynı veri üzerinde tekrar tekrar arama yapılacaksa veriyi bir kez düzenlemek, uygun bir veri yapısı seçmek ve arama sıklığını hesaba katmak daha anlamlı olabilir.
Sonuç olarak binary search her durumda kullanılmaz; doğru sıralama, tutarlı karşılaştırma ve güvenilir eleme koşulları bulunduğunda güçlü ve sistematik bir tercihtir. Bu kontrol listesi, algoritmayı ezbere seçmek yerine veri düzeni ile kullanım amacını birlikte düşünmenizi sağlar.
Sık Sorulan Sorular
Binary search sıralanmamış bir listede neden güvenilir çalışmaz?
Çünkü algoritma, orta değeri hedefle karşılaştırdıktan sonra listenin hangi yarısının eleneceğine karar verir. Liste sıralı değilse orta değerin hedefin önünde veya arkasında olması, hedefin hangi tarafta bulunduğunu göstermez. Bu nedenle bir yarıyı elemek yanlış sonuca yol açabilir.
Binary search ile doğrusal arama arasındaki temel fark nedir?
Doğrusal arama elemanları sırayla kontrol eder. Binary search ise sıralı bir arama alanının ortasına bakar ve her adımda uygun olmayan bir bölümü eler. Bu yüzden iki algoritmanın kullanılabileceği koşullar aynı değildir: Binary search için sıralama ve karşılaştırılabilirlik gerekir.
Binary search hedef değeri bulamazsa ne döndürür?
Bu, fonksiyonun nasıl tasarlandığına bağlıdır. Yaygın bir uygulamada hedef bulunamadığında False veya None döndürülür. Bazı uygulamalar ise hedefin bulunması gereken konumu ya da ekleme indeksini belirtir. Önemli olan, bulunamama durumunun açıkça tanımlanmasıdır.
Tek elemanlı veya çift elemanlı listelerde binary search çalışır mı?
Evet, çalışır. Tek elemanlı listede orta konumdaki tek değer kontrol edilir. Çift elemanlı listede ise iki orta konumdan biri, kullanılan indeks hesaplama kuralına göre seçilir. Her iki durumda da sınırlar doğru güncellendiği sürece algoritma güvenilir biçimde ilerler.
Bir arama probleminde binary search kullanıp kullanmayacağımı nasıl anlarım?
Önce verinin sıralı olup olmadığını ve hedef ile orta değerin aynı ölçüte göre karşılaştırılıp karşılaştırılamadığını kontrol edin. Ardından her adımda bir yarının güvenilir biçimde elenip elenemeyeceğine bakın. Liste sıralı değilse, veri küçük ve arama tek seferlikse doğrusal arama daha uygun olabilir.
Binary search seçimi, yalnızca algoritmayı bilmekle değil, verinin nasıl düzenlendiğini ve aramanın hangi amaçla yapılacağını doğru değerlendirmekle ilgilidir.
