Binary Search

Q: İkili aramanın zaman karmaşıklığı nedir?

O(log n) . Her karşılaştırma, hedefi hâlâ içerebilecek aralığı yarıya indirir; bu nedenle k adımdan sonra en fazla n / 2^k aday kalır. 10^4 elemanlı bir liste en fazla 14 karşılaştırma, 10^9 elemanlı bir liste ise en fazla 30 karşılaştırma gerektirir. Yinelemeli sürüm O(1) ek alan kullanır.

Q: İkili arama neden sıralı bir dizi gerektirir?

Listenin yarısını eleyen adım sıralamaya dayanır. nums[mid] < target olduğunda sıralama, mid değerinin solundaki her öğenin de target değerinden küçük olduğunu garanti eder; bu nedenle hiçbiri eşleşemez. Sıralanmamış bir listede bu karşılaştırma diğer öğeler hakkında hiçbir şey söylemez ve hepsini kontrol etmeniz gerekir.

Q: İkili arama yinelemeli mi yoksa özyinelemeli mi olmalı?

İkisi de doğrudur ve ikisi de O(log n) zamanda çalışır. Özyinelemeli sürüm, kendisini yarılardan biri üzerinde çağırır ve O(log n) yığın alanı kullanır; yinelemeli sürüm ise bir döngüde lo ve hi değerlerini hareket ettirir ve O(1) kullanır. Görüşmeciler genellikle döngüyü bekler ve bu, herhangi bir özyineleme sınırını aşmayı önler.

Q: Orta indeksi hesaplarken taşmayı nasıl önlersiniz?

mid = lo + (hi - lo) / 2 yazın, (lo + hi) / 2 yerine. İkisi de aynı indeksi verir, ancak ikinci biçim önce iki indeksi toplar ve 32 bitlik bir tamsayıda, indeksler yaklaşık 1.07 × 10^9 değerini geçtiğinde bu toplam taşar. Python ve Ruby'de tamsayıların üst sınırı yoktur, bu nedenle kısa biçim burada güvenlidir.

Kolayİkili arama

+10

Tekrarlanan değer içermeyen, artan sırada sıralanmış bir tam sayılar listesi olan nums ve bir tam sayı olan target veriliyor. target değerinin nums içindeki indeksini 0'dan başlayarak döndürün veya listede yoksa -1 döndürün. O(log n) zaman hedefleyin; bu, her öğeye bakmayı göze alamayacağınız anlamına gelir.

Fonksiyon

search(nums: integer-array, target: integer) → integer

numsinteger-array: sıralanmış farklı tam sayılar listesi
targetinteger: aranacak değer
Döndürürinteger: nums içinde target'ın indeksi; yoksa -1

Kısıtlar

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i], target ≤ 10⁴
nums kesin artan sırada sıralanmıştır, bu nedenle her değer bir kez görünür.

Örnekler

Girdi: nums = [-7, -2, 0, 4, 9, 15, 23]target = 9
Çıktı: 4
Açıklama: nums[4] 9'dur. Arama, 3. indekse bakar (değer 4, çok küçük), sonra 5. indekse (değer 15, çok büyük), ardından 9'u bulduğu 4. indekse bakar.

Girdi: nums = [1, 3, 5, 8, 13, 21]target = 10
Çıktı: -1
Açıklama: 10, 8 ile 13 arasında yer alır ve hiçbiri 10 değildir; bu nedenle listede bulunmaz. Arama aralığı, lo hi'yi geçene kadar daralır ve işlev -1 döndürür.

Gönderirken +15 gizli test

Ek soru

Eğer nums içinde değerler tekrarlanabiliyorsa, yine O(log n) sürede target değerinin ilk indeksini nasıl döndürürdün?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Öğeleri tek tek okumak target değerini bulur, ancak problemi ilginç kılan tek bir gerçeği göz ardı eder: liste sıralıdır. Ortadaki öğeyle yapılacak tek bir karşılaştırma, hangi yarıda hâlâ target bulunabileceğini gösterir; böylece her adımda adayların yarısını eleyebilirsin. Bu durumda 10^4 öğeli bir liste, 10000 yerine en fazla 14 karşılaştırma gerektirir.

Soldan sağa tara

Sezgi

Her indeksi sırayla kontrol et ve değeri target değerine eşit olan ilk indeksi döndür. Eşleşme bulunmadan döngü sona ererse target listede değildir; bu yüzden -1 döndür. Her öğe bir kez karşılaştırılır; bu da yanıtın sıralı olsun ya da olmasın her liste için doğru olmasını sağlar.

Bu genellik sorunun kendisidir. 10^4 öğeli bir liste en fazla 10000 karşılaştırma gerektirir ve yapılan iş n ile orantılı olarak artar. Tarama, nums listesinin sıralı olmasından yararlanmadığı için görevin istediği O(log n) sınırını yakalayamaz. Bir değer target değerini geçtiğinde taramayı erken durdurabilirsin; ancak en kötü durumda yine de listenin tamamını okursun.

Algoritma

0'dan n-1'e kadar her indeks i için nums[i] ile target'ı karşılaştır.
Eşitlerse i'yi döndür.
Döngüden sonra -1'i döndür.

def search(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i
    return -1

İki indeksle ikili arama

Sezgi

İki indeks tut: lo ve hi. Şu koşulu garanti et: target listede varsa indeksi, uçlar da dahil olmak üzere lo ile hi arasındadır. Başlangıçta bu aralık, 0'dan n-1'e kadar listenin tamamıdır. Ortadaki indekse, yani mid'e bak. nums[mid], target'a eşitse işlem tamamdır. Daha küçükse, liste sıralı olduğundan mid'e kadar olan her eleman da daha küçüktür; bu yüzden lo'yu mid + 1 yap. Daha büyükse hi'yi mid - 1 yap. Her iki güncellemeden sonra da koşul geçerliliğini korur.

İlk örneği izle: [-7, -2, 0, 4, 9, 15, 23] ve target = 9. 0'dan 6'ya kadar olan aralığın ortası 3'tür; buradaki değer 4, yani çok küçüktür. Bu yüzden aralık 4'ten 6'ya dönüşür. Ortası 5 olan bu aralıkta 15 vardır; bu da çok büyüktür. Dolayısıyla aralık 4'ten 4'e dönüşür. 4. indekste 9 vardır: 4 değerini döndür.

target listede yoksa aralık, lo hi'yi geçene kadar daralmaya devam eder. Aralık bu noktada boştur; koşul, target'ın hiçbir yerde olmadığını gösterir ve -1 döndürürsün. Her adımda aralık yarıya iner; bu nedenle döngü en fazla yaklaşık log2(n) + 1 kez çalışır: 10^4 eleman için 14 adım. İhtiyacın olan ek bellek yalnızca iki indekstir.

Algoritma

lo = 0 ve hi = n-1 olarak ayarla.
lo ≤ hi olduğu sürece mid = lo + (hi - lo) / 2 değerini hesapla.
nums[mid], target'a eşitse mid değerini döndür.
nums[mid] < target ise lo = mid + 1 olarak ayarla; aksi takdirde hi = mid - 1 olarak ayarla.
Döngü sona erdiğinde -1 döndür.

def search(nums, target):
    lo, hi = 0, len(nums) - 1  # target, if present, sits in nums[lo..hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1  # nums[mid] and everything left of it is too small
        else:
            hi = mid - 1  # nums[mid] and everything right of it is too big
    return -1

Tuzaklar ve uç durumlar

İkili arama kısadır ve hataların neredeyse tamamı aralığın sınırlarındaki birer birimlik kaymalardan kaynaklanır.

hi son indekse ayarlanmışken lo < hi koşuluyla döngü kurmak. Bir aday henüz kontrol edilmemişken döngü durur; bu yüzden nums = [5] ve target = 5 için -1 döner. Uçları dahil eden bir aralıkla lo ≤ hi koşuluyla döngü kur.
Uçları dahil eden bir aralıkla lo = mid veya hi = mid değerlerini atamak. lo ile hi komşu olduğunda mid, lo'ya eşit olur ve aralık hiç daralmaz: sonsuz döngü. nums[mid] değerini zaten kontrol ettin; bu yüzden mid + 1 veya mid - 1 ile ötesine geç.
Sabit genişlikli bir tamsayıda (lo + hi) / 2 hesaplamak. İndeksler yaklaşık 10^9 değerini geçtiğinde toplam taşar. Buradaki sınırlar bunun çok altındadır, ancak lo + (hi - lo) / 2 güvenli bir alışkanlıktır.
target bulunamadığında lo değerini döndürmek. Döngüden sonra lo, geçerli bir indeks olan ekleme noktasını gösterir; -1 değerini değil.
Lua ve R'deki kaydırmayı unutmak. Listeleri 1'den başlar, bu nedenle döndüreceğin indeks, konum eksi 1'dir.

Sıkça sorulan sorular4

İkili aramanın zaman karmaşıklığı nedir?

O(log n). Her karşılaştırma, hedefi hâlâ içerebilecek aralığı yarıya indirir; bu nedenle k adımdan sonra en fazla n / 2^k aday kalır. 10^4 elemanlı bir liste en fazla 14 karşılaştırma, 10^9 elemanlı bir liste ise en fazla 30 karşılaştırma gerektirir. Yinelemeli sürüm O(1) ek alan kullanır.

İkili arama neden sıralı bir dizi gerektirir?

Listenin yarısını eleyen adım sıralamaya dayanır. nums[mid] < target olduğunda sıralama, mid değerinin solundaki her öğenin de target değerinden küçük olduğunu garanti eder; bu nedenle hiçbiri eşleşemez. Sıralanmamış bir listede bu karşılaştırma diğer öğeler hakkında hiçbir şey söylemez ve hepsini kontrol etmeniz gerekir.

İkili arama yinelemeli mi yoksa özyinelemeli mi olmalı?

İkisi de doğrudur ve ikisi de O(log n) zamanda çalışır. Özyinelemeli sürüm, kendisini yarılardan biri üzerinde çağırır ve O(log n) yığın alanı kullanır; yinelemeli sürüm ise bir döngüde lo ve hi değerlerini hareket ettirir ve O(1) kullanır. Görüşmeciler genellikle döngüyü bekler ve bu, herhangi bir özyineleme sınırını aşmayı önler.

Orta indeksi hesaplarken taşmayı nasıl önlersiniz?

mid = lo + (hi - lo) / 2 yazın, (lo + hi) / 2 yerine. İkisi de aynı indeksi verir, ancak ikinci biçim önce iki indeksi toplar ve 32 bitlik bir tamsayıda, indeksler yaklaşık 1.07 × 10^9 değerini geçtiğinde bu toplam taşar. Python ve Ruby'de tamsayıların üst sınırı yoktur, bu nedenle kısa biçim burada güvenlidir.

Python

def search(nums, target):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Girdi

nums = [-7, -2, 0, 4, 9, 15, 23]
target = 9

Beklenen