Binary Search
Searches by repeatedly cutting the search space in half.
The Approach
- Ensure the data is sorted.
- Initialize low and high pointers, usually at the start and end of the search space.
- While low <= high, calculate the middle index.
- If the middle element is the target, you're done.
- If the middle element is smaller than the target, discard the left half by moving the low pointer.
- If the middle element is larger, discard the right half by moving the high pointer.
Types of Binary Search
Search on Index
The standard binary search performed on a sorted array to find an element's position.
10
20
30
40
50
60
70
80
90
L
H
Initialize pointers.
Search on Answer
Used for optimization problems where the answer lies in a range, and you can test if a potential answer 'mid' is feasible.
10
20
30
40
50
60
70
80
90
L
H
Initialize pointers.
Common Problems
Binary Search
Binary Search
First Bad Version
Binary Search
Find First and Last Position of Element in Sorted Array
Binary Search
Search Insert Position
Binary Search
Capacity To Ship Packages Within D Days
Binary Search