Typowe błędy to niespójne granice (pętla nieskończona) i overflow przy liczeniu środka. Użyj `mid = left + (right - left) / 2` i trzymaj się konsekwentnie zakresu (inclusive/exclusive).
function binarySearch(arr: number[], target: number): number {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}Binary search to przede wszystkim inwarianty. Wybierz jedną konwencję granic i trzymaj się jej konsekwentnie.
Bardzo bezpieczny wariant to przedział półotwarty [l, r):
function lowerBound(a: number[], x: number) {
let l = 0, r = a.length
while (l < r) {
const mid = l + Math.floor((r - l) / 2)
if (a[mid] >= x) r = mid
else l = mid + 1
}
return l
}