16.03Beginner / Intermediate6 topics22 min6 interactive animations

Binary search variants

Most binary search problems are variations on one template: keep a window that must contain the answer, and decide which half can be dropped. These variants cover the shapes that come up most often.

Learning goals

Map insert position, floor and ceiling onto lower bound
Find the closest value with one binary search and one comparison
Search rotated and nearly sorted arrays in O(log n)
Find a peak without the array being sorted at all

Prerequisites

Iterative binary searchLower and upper bound

Real data is rarely a clean sorted list with an exact match. You may need the nearest price, a log that was rotated at midnight, or a local maximum in a signal.

16.03.1

Insert position

The insert position of x is the index where x would go to keep the array sorted. That is exactly lower bound: the first index with arr[i] >= x.

If x is already present, lower bound returns the index of its first copy, which is also a valid insert position. Run the lower-bound animation with “Between values” and “Larger than all” to see both kinds of answer.

Java

1int pos = Arrays.binarySearch(arr, x);
2if (pos < 0) pos = -pos - 1;   // JDK encodes the insertion point as -(pos) - 1

Lower bound

Interactive · edit the input

int[] arr · length 8

012345678

Being comparedNot a matchDiscardedMatch / answer

Setup

Find the first index with arr[i] >= 3. hi starts at arr.length (8) because the answer may be "past the end".

Step 1 / 19

Java

1public static int lowerBound(int[] arr, int target) {
2    int lo = 0, hi = arr.length;      // half-open window [lo, hi)
3    while (lo < hi) {
4        int mid = lo + (hi - lo) / 2;
5        if (arr[mid] < target) {
6            lo = mid + 1;
7        } else {
8            hi = mid;
9        }
10    }
11    return lo;
12}

Live state

0 probes

target

No condition evaluated on this step

Execution trace (dry run table)Show 19 steps

Step	Line	State	What happens
1	L2	target=3 lo=0 hi=8	Find the first index with arr[i] >= 3. hi starts at arr.length (8) because the answer may be "past the end".
2	L3	target=3 lo=0 hi=8	The answer is somewhere in [0, 8].
3	L4	target=3 lo=0 hi=8 mid=4	mid = 4.
4	L5	target=3 lo=0 hi=8 mid=4 arr[mid]=6	arr[4] could be the answer. Keep it, but look further left.
5	L8	target=3 lo=0 hi=4	hi = mid = 4. mid stays inside the window as a candidate.
6	L3	target=3 lo=0 hi=4	The answer is somewhere in [0, 4].
7	L4	target=3 lo=0 hi=4 mid=2	mid = 2.
8	L5	target=3 lo=0 hi=4 mid=2 arr[mid]=3	arr[2] could be the answer. Keep it, but look further left.
9	L8	target=3 lo=0 hi=2	hi = mid = 2. mid stays inside the window as a candidate.
10	L3	target=3 lo=0 hi=2	The answer is somewhere in [0, 2].
11	L4	target=3 lo=0 hi=2 mid=1	mid = 1.
12	L5	target=3 lo=0 hi=2 mid=1 arr[mid]=3	arr[1] could be the answer. Keep it, but look further left.
13	L8	target=3 lo=0 hi=1	hi = mid = 1. mid stays inside the window as a candidate.
14	L3	target=3 lo=0 hi=1	The answer is somewhere in [0, 1].
15	L4	target=3 lo=0 hi=1 mid=0	mid = 0.
16	L5	target=3 lo=0 hi=1 mid=0 arr[mid]=1	arr[0] cannot be the answer, nor anything to its left.
17	L6	target=3 lo=1 hi=1	lo = 1.
18	L3	target=3 lo=1 hi=1	lo == hi == 1: the window has collapsed onto the answer.
19	L11	target=3 return=1	return 1: arr[1] = 3 is the first index with arr[i] >= 3. Inserting 3 here keeps the array sorted.

16.03.2

Floor and ceiling

The floor of x is the largest element <= x; the ceiling is the smallest element >= x. Either may not exist, in which case return -1.

Both use the “record a candidate and keep searching” pattern. For floor, a qualifying arr[mid] is saved, then we look right for a larger one. Ceiling is the mirror image.

Query on [2, 6, 9, 13, 18]	Floor	Ceiling
x = 10	9	13
x = 13	13	13
x = 1	none	2
x = 20	18	none

Floor (largest ≤ target)

Interactive · edit the input

int[] arr · length 7

0123456

Being comparedNot a matchCandidateDiscardedMatch / answer

Setup

Find the largest element <= 15.

Step 1 / 16

Java

1public static int floorIndex(int[] arr, int target) {
2    int lo = 0, hi = arr.length - 1, ans = -1;
3    while (lo <= hi) {
4        int mid = lo + (hi - lo) / 2;
5        if (arr[mid] <= target) {
6            ans = mid;              // candidate floor
7            lo = mid + 1;           // try for a larger one
8        } else {
9            hi = mid - 1;
10        }
11    }
12    return ans;
13}

Live state

0 probes

target

ans

-1

No condition evaluated on this step

Execution trace (dry run table)Show 16 steps

Step	Line	State	What happens
1	L2	target=15 lo=0 hi=6 ans=-1	Find the largest element <= 15.
2	L3	target=15 lo=0 hi=6 ans=-1	Search [0, 6].
3	L4	target=15 lo=0 hi=6 ans=-1 mid=3	mid = 3.
4	L5	target=15 lo=0 hi=6 ans=-1 mid=3 arr[mid]=13	13 qualifies as a floor candidate.
5	L6	target=15 lo=0 hi=6 ans=3 mid=3	ans = 3 (value 13).
6	L7	target=15 lo=4 hi=6 ans=3	lo = 4: a larger qualifying value may exist to the right.
7	L3	target=15 lo=4 hi=6 ans=3	Search [4, 6].
8	L4	target=15 lo=4 hi=6 ans=3 mid=5	mid = 5.
9	L5	target=15 lo=4 hi=6 ans=3 mid=5 arr[mid]=25	25 cannot be the floor.
10	L9	target=15 lo=4 hi=4 ans=3	hi = 4.
11	L3	target=15 lo=4 hi=4 ans=3	Search [4, 4].
12	L4	target=15 lo=4 hi=4 ans=3 mid=4	mid = 4.
13	L5	target=15 lo=4 hi=4 ans=3 mid=4 arr[mid]=18	18 cannot be the floor.
14	L9	target=15 lo=4 hi=3 ans=3	hi = 3.
15	L3	target=15 lo=4 hi=3 ans=3	Window empty, ans holds the answer.
16	L12	target=15 return=3	return 3: the floor of 15 is 13.

Ceiling (smallest ≥ target)

Interactive · edit the input

int[] arr · length 7

0123456

Being comparedNot a matchCandidateDiscardedMatch / answer

Setup

Find the smallest element >= 15.

Step 1 / 17

Java

1public static int ceilingIndex(int[] arr, int target) {
2    int lo = 0, hi = arr.length - 1, ans = -1;
3    while (lo <= hi) {
4        int mid = lo + (hi - lo) / 2;
5        if (arr[mid] >= target) {
6            ans = mid;              // candidate ceiling
7            hi = mid - 1;           // try for a smaller one
8        } else {
9            lo = mid + 1;
10        }
11    }
12    return ans;
13}

Live state

0 probes

target

ans

-1

No condition evaluated on this step

Execution trace (dry run table)Show 17 steps

Step	Line	State	What happens
1	L2	target=15 lo=0 hi=6 ans=-1	Find the smallest element >= 15.
2	L3	target=15 lo=0 hi=6 ans=-1	Search [0, 6].
3	L4	target=15 lo=0 hi=6 ans=-1 mid=3	mid = 3.
4	L5	target=15 lo=0 hi=6 ans=-1 mid=3 arr[mid]=13	13 cannot be the ceiling.
5	L9	target=15 lo=4 hi=6 ans=-1	lo = 4.
6	L3	target=15 lo=4 hi=6 ans=-1	Search [4, 6].
7	L4	target=15 lo=4 hi=6 ans=-1 mid=5	mid = 5.
8	L5	target=15 lo=4 hi=6 ans=-1 mid=5 arr[mid]=25	25 qualifies as a ceiling candidate.
9	L6	target=15 lo=4 hi=6 ans=5 mid=5	ans = 5 (value 25).
10	L7	target=15 lo=4 hi=4 ans=5	hi = 4: a smaller qualifying value may exist to the left.
11	L3	target=15 lo=4 hi=4 ans=5	Search [4, 4].
12	L4	target=15 lo=4 hi=4 ans=5 mid=4	mid = 4.
13	L5	target=15 lo=4 hi=4 ans=5 mid=4 arr[mid]=18	18 qualifies as a ceiling candidate.
14	L6	target=15 lo=4 hi=4 ans=4 mid=4	ans = 4 (value 18).
15	L7	target=15 lo=4 hi=3 ans=4	hi = 3: a smaller qualifying value may exist to the left.
16	L3	target=15 lo=4 hi=3 ans=4	Window empty, ans holds the answer.
17	L12	target=15 return=4	return 4: the ceiling of 15 is 18.

16.03.3

Closest element

The closest element is either the first element >= x or the one just before it. Binary search finds the first candidate, then one comparison of distances picks the winner.

Define the tie rule explicitly. The animation picks the smaller value when distances are equal.

Closest element

Interactive · edit the input

int[] arr · length 7

0123456

Being comparedNot a matchCandidateDiscardedMatch / answer

Setup

Step 1: find the first element >= 19 (clamped to the last index).

Step 1 / 13

Java

1public static int closest(int[] arr, int target) {
2    int lo = 0, hi = arr.length - 1;
3    while (lo < hi) {
4        int mid = lo + (hi - lo) / 2;
5        if (arr[mid] < target) {
6            lo = mid + 1;
7        } else {
8            hi = mid;
9        }
10    }
11    if (lo > 0 && Math.abs(arr[lo - 1] - target) <= Math.abs(arr[lo] - target)) {
12        return lo - 1;
13    }
14    return lo;
15}

Live state

0 probes

target

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L2	target=19 lo=0 hi=6	Step 1: find the first element >= 19 (clamped to the last index).
2	L3	target=19 lo=0 hi=6	Search [0, 6].
3	L5	target=19 lo=0 hi=6 mid=3 arr[mid]=15	mid = 3. Too small, go right.
4	L6	target=19 lo=4 hi=6	lo = 4.
5	L3	target=19 lo=4 hi=6	Search [4, 6].
6	L5	target=19 lo=4 hi=6 mid=5 arr[mid]=30	mid = 5. Could be the first >= target, keep it.
7	L8	target=19 lo=4 hi=5	hi = 5.
8	L3	target=19 lo=4 hi=5	Search [4, 5].
9	L5	target=19 lo=4 hi=5 mid=4 arr[mid]=22	mid = 4. Could be the first >= target, keep it.
10	L8	target=19 lo=4 hi=4	hi = 4.
11	L3	target=19 lo=4 hi=4	Converged on index 4.
12	L11	target=19 lo=4 \|left-target\|=4 \|arr[lo]-target\|=3	Step 2: the closest value is either arr[lo] or its left neighbour. Compare distances (ties go left).
13	L14	target=19 return=4	return 4: 22 is closest to 19 (distance 3).

16.03.4

Rotated sorted array

A rotated sorted array such as [15, 18, 22, 27, 3, 6, 9, 12] is sorted, then cut and swapped. Whatever mid you pick, at least one of the halves [lo..mid] or [mid..hi] is still sorted.

Check which half is sorted by comparing arr[lo] with arr[mid]. Then test whether the target falls inside that sorted half's range. If it does, search there; otherwise search the other half.

Best

O(1)

Worst

O(log n)

Space

O(1)

Search in a rotated sorted array

Interactive · edit the input

int[] arr · length 8

01234567

Being comparedCandidateNot a matchDiscardedMatch / answer

Setup

The array was sorted, then rotated. At every step at least one half of the window is still sorted.

Step 1 / 7

Java

1public static int searchRotated(int[] arr, int target) {
2    int lo = 0, hi = arr.length - 1;
3    while (lo <= hi) {
4        int mid = lo + (hi - lo) / 2;
5        if (arr[mid] == target) return mid;
6        if (arr[lo] <= arr[mid]) {                      // left half sorted
7            if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
8            else lo = mid + 1;
9        } else {                                        // right half sorted
10            if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
11            else hi = mid - 1;
12        }
13    }
14    return -1;
15}

Live state

0 probes

target

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L2	target=6 lo=0 hi=7	The array was sorted, then rotated. At every step at least one half of the window is still sorted.
2	L5	target=6 lo=0 hi=7 mid=3 arr[mid]=27	mid = 3. Not the target.
3	L6	target=6 lo=0 hi=7 mid=3	Left half [0..3] is sorted (highlighted).
4	L7	target=6 lo=0 hi=7 mid=3	Target is not in the sorted left half. Search the right half.
5	L8	target=6 lo=4 hi=7	lo = 4.
6	L5	target=6 lo=4 hi=7 mid=5 arr[mid]=6	mid = 5. Match.
7	L5	target=6 return=5	return 5.

16.03.5

Peak element

A peak is an element larger than its neighbours, treating the ends as -∞. The array does not need to be sorted.

Compare arr[mid] with arr[mid + 1]. If the slope goes up, a peak must exist to the right, because the values cannot rise forever. Otherwise a peak exists at mid or to its left. Either way half the window is discarded.

The algorithm finds a peak, not necessarily the highest one. Try the “Two peaks” preset.
The same idea finds the peak of a mountain (bitonic) array.

Worst

O(log n)

Space

O(1)

Find a peak element

Interactive · edit the input

int[] arr · length 9

012345678

Being comparedNot a matchDiscardedMatch / answer

Setup

A peak is larger than its neighbours. Imagine both ends are -∞, so a peak always exists.

Step 1 / 12

Java

1public static int findPeak(int[] arr) {
2    int lo = 0, hi = arr.length - 1;
3    while (lo < hi) {
4        int mid = lo + (hi - lo) / 2;
5        if (arr[mid] < arr[mid + 1]) {
6            lo = mid + 1;     // uphill to the right
7        } else {
8            hi = mid;         // mid is on a peak or a downhill slope
9        }
10    }
11    return lo;
12}

Live state

0 probes

No condition evaluated on this step

Execution trace (dry run table)Show 12 steps

Step	Line	State	What happens
1	L2	lo=0 hi=8	A peak is larger than its neighbours. Imagine both ends are -∞, so a peak always exists.
2	L3	lo=0 hi=8	A peak is guaranteed inside [0, 8].
3	L5	lo=0 hi=8 mid=4 arr[mid]=11 arr[mid+1]=7	The slope falls (or mid is a peak), so a peak exists at mid or to its left.
4	L8	lo=0 hi=4	hi = 4.
5	L3	lo=0 hi=4	A peak is guaranteed inside [0, 4].
6	L5	lo=0 hi=4 mid=2 arr[mid]=9 arr[mid+1]=14	The slope rises to the right, so a peak must exist on the right.
7	L6	lo=3 hi=4	lo = 3.
8	L3	lo=3 hi=4	A peak is guaranteed inside [3, 4].
9	L5	lo=3 hi=4 mid=3 arr[mid]=14 arr[mid+1]=11	The slope falls (or mid is a peak), so a peak exists at mid or to its left.
10	L8	lo=3 hi=3	hi = 3.
11	L3	lo=3 hi=3	Window narrowed to one index.
12	L11	return=3	return 3: arr[3] = 14 is a peak, found in 3 probes.

16.03.6

Nearly sorted array

In a nearly sorted array, each element is at most one position away from where it would be in sorted order, e.g. [3, 2, 10, 4, 40, 20].

Check mid, mid - 1 and mid + 1. If none match, the three checked slots are done, so move lo to mid + 2 or hi to mid - 2.

Worst

O(log n)

Space

O(1)

Search in a nearly sorted array

Interactive · edit the input

int[] arr · length 8

01234567

Being comparedNot a matchDiscardedMatch / answer

Setup

Each element may sit one slot left or right of its sorted position, so check mid and both neighbours.

Step 1 / 3

Java

1public static int searchNearlySorted(int[] arr, int target) {
2    int lo = 0, hi = arr.length - 1;
3    while (lo <= hi) {
4        int mid = lo + (hi - lo) / 2;
5        if (arr[mid] == target) return mid;
6        if (mid > lo && arr[mid - 1] == target) return mid - 1;
7        if (mid < hi && arr[mid + 1] == target) return mid + 1;
8        if (arr[mid] < target) lo = mid + 2;
9        else hi = mid - 2;
10    }
11    return -1;
12}

Live state

0 probes

target

No condition evaluated on this step

Execution trace (dry run table)Show 3 steps

Step	Line	State	What happens
1	L2	target=4 lo=0 hi=7	Each element may sit one slot left or right of its sorted position, so check mid and both neighbours.
2	L5	target=4 lo=0 hi=7 mid=3 arr[3]=4	mid = 3. Check mid first.
3	L5	target=4 return=3	return 3.

Practice ladder

Now try it yourself

Easy

Search insert position
Find the floor of a value in a sorted array
Find a peak element

Medium

Search in a rotated sorted array
Find the minimum in a rotated sorted array
Find K closest elements

Advanced

Search in a rotated array with duplicates
Find a peak element in a 2D grid
Single element in a sorted array where all others appear twice

Key takeaways

Insert position, floor and ceiling are lower and upper bound in disguise.
Record a candidate, then keep shrinking toward the better side.
Binary search only needs a rule that safely discards half of the window, not a fully sorted array.