DSA Basics: Binary Search

Binary search is an efficient search algorithm for sorted arrays. Instead of checking every value, it repeatedly cuts the search area in half.

The important condition is that the input must be sorted. If the values are not sorted, binary search cannot safely decide which half to discard.

Core idea

Keep two pointers:

• left starts at the beginning.
• right starts at the end.
• mid points to the middle.

If values[mid] is too small, move left to mid + 1. If it is too large, move right to mid - 1.

function binarySearch(values, target) {
	let left = 0;
	let right = values.length - 1;

	while (left <= right) {
		const mid = Math.floor((left + right) / 2);

		if (values[mid] === target) return mid;
		if (values[mid] < target) left = mid + 1;
		else right = mid - 1;
	}

	return -1;
}

Why it is fast

Every step removes half of the remaining search space. For 1,000,000 sorted values, binary search needs about 20 checks, not one million.

Complexity

• Time: O(log n)
• Space: O(1) for the iterative version

Common mistakes

• Running binary search on an unsorted array.
• Writing left < right when the final single value still needs checking.
• Updating left = mid instead of left = mid + 1, which can cause an infinite loop.
• Forgetting that integer midpoint calculation must round down.

Practice problems

1. Search a sorted array.
2. Find the first occurrence of a value.
3. Find the last occurrence of a value.
4. Find the insert position for a target.
5. Find the smallest value greater than or equal to a target.

Practice links

• LeetCode Binary Search problems
• NeetCode practice roadmap