Find the index of a target in a SORTED array in O(log n) by repeatedly halving the search range.
Maintain low and high bounds; compute mid, compare to the target, and discard the half that cannot contain it. Compute mid as low + (high - low) / 2 to avoid integer overflow. Requires a sorted array. O(log n).
public static int binarySearch(int[] a, int target) {
int low = 0, high = a.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (a[mid] == target) return mid;
if (a[mid] < target) low = mid + 1; else high = mid - 1;
}
return -1;
}function binarySearch(a, target) {
let low = 0, high = a.length - 1;
while (low <= high) {
const mid = (low + high) >> 1;
if (a[mid] === target) return mid;
if (a[mid] < target) low = mid + 1; else high = mid - 1;
}
return -1;
}def binary_search(a, target):
low, high = 0, len(a) - 1
while low <= high:
mid = (low + high) // 2
if a[mid] == target:
return mid
if a[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1Binary search powers lookups in sorted indexes, version bisection (git bisect), and any "find the boundary" search over a monotonic space.
In Java, why prefer mid = low + (high - low)/2 over (low + high)/2?