Easy Searching
Binary Search
Receives a sorted array of integers and a target value. It looks at the middle element of the current range: if it equals the target the search ends; if the target is smaller it continues in the left half, otherwise in the right half — halving the range each step because the array is already ordered. Returns the index (position) where the target is found, or -1 if it is not present.
Visualization
- Input
- Result
Algorithm code
// Binary Search — a single pure function. Receives a sorted array and a target,
// returns the index of the target, or -1 if it is not present.
/**
* @param {number[]} arr - sorted array of integers
* @param {number} target - value to find
* @returns {number} index of target, or -1 if absent
*/
export function binarySearch(arr, target) {
let lo = 0;
let hi = arr.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) {
return mid;
}
if (arr[mid] < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1;
}FUNCTION binarySearch(arr, target):
lo ← 0
hi ← length(arr) - 1
WHILE lo ≤ hi:
mid ← floor((lo + hi) / 2)
IF arr[mid] = target:
RETURN mid
ELSE IF arr[mid] < target:
lo ← mid + 1
ELSE:
hi ← mid - 1
RETURN -1