İkili Arama
Arama O(log n) O(1)Ortadaki elemanı hedefle karşılaştırarak sıralı aralığı her adımda ikiye böler.
3
7
9
15
23
28
34
41
8 elemanlı sıralı dizide 15 aranıyor.
DeğişmezHedef varsa [0..7] aralığındadır — dışarıdaki her şey yalnızca sıralılık sayesinde elendi.
1/3
sondaj0lo0hi7mid0
binary-search.c
int binarySearch(int arr[], int n, int target) {int lo = 0, hi = n - 1;while (lo <= hi) {int mid = lo + (hi - lo) / 2;if (arr[mid] == target)return mid;if (arr[mid] < target)lo = mid + 1;elsehi = mid - 1;}return -1;}
İkili Arama nasıl çalışır?
Hedefi sıralı aralığın ortasıyla karşılaştır. Tek karşılaştırma kalan adayların yarısını eler; kalan yarıda tekrarla.
En iyi durum
Hedef tam ortada: O(1).
En kötü durum
Tek eleman kalana dek yarılama: O(log n).
Ne zaman kullanılır?
Her sıralı dizi — ayrıca lower/upper-bound aramalarının yapı taşı.