Wyszukiwanie binarne znajduje element w posortowanej tablicy/liście, porównując go ze środkiem i odrzucając połowę zakresu w każdym kroku. Wymaga danych posortowanych i działa w czasie O(log n) (iteracyjnie zużywa O(1) pamięci).
function binarySearch(arr: number[], target: number): number {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}Rozwinięcie krótkiej odpowiedzi — co zwykle ma znaczenie w praktyce:
Poniżej dodatkowy przykład (bazuje na tym, co już jest w odpowiedzi):
function binarySearch(arr: number[], target: number): number {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}