DSA Notes

Techniques

Binary Search

Halve the search space with every question.

The idea

Binary search needs a yes/no question whose answers are monotone: no, no, …, no, yes, yes, …, yes. It finds the first yes in O(log n) steps.

On a sorted array, “is a[i] ≥ x?” is such a question. The library has it built in: lower_bound returns the first element ≥ x and upper_bound the first element > x; their difference counts the copies of x.

In interactive problems each query is expensive and the limit is around log₂ of the range, which is the hint to halve.

Sample problem

704. Binary Search ↗ Easy

Given a sorted array of distinct integers and a target, return the index of the target, or −1 if it is not there. The algorithm must run in O(log n).

nums = [1,3,5,7,9,11,13,15,17,19,21], target = 13
output = 6

Why the solution works

Because the array is sorted, one comparison with the middle element tells which half can still contain the target. The other half is discarded without being read.

The range of candidates halves every step, so after about log₂ n steps it is empty or the target is found. For a million elements that is 20 comparisons.

Complexity: O(log n) time, O(1) memory.

Watch out

  • Writing lo = mid with a rounded-down mid loops forever when hi = lo + 1. Keep an answer variable and always move past mid.
  • (lo + hi) / 2 can overflow; use lo + (hi - lo) / 2.
  • The array must be sorted by the same order you search with.
Watch it run

Try your own input

Practise on LeetCode