bisect_left, bisect_right

Easy Binary Search Bisect

bisect_left, bisect_right is a easy binary search problem solved with the bisect pattern. The best approach, optimal (half-open binary search), runs in O(log n) time and O(1) space. Below are 2 approaches in Java, from linear scan up.

Problem

bisect_left(a, x) returns the leftmost position where x could be inserted into sorted a while keeping it sorted. bisect_right(a, x) returns the rightmost such position. Named after Python’s bisect module, these two functions solve most of the problems in this pattern.

Examples

Example 1

Input: a = [1, 3, 3, 3, 8], x = 3
Output: bisect_left = 1, bisect_right = 4
Why: Insert before the 3s at 1, or after them at 4. right - left = 3 copies.

Example 2

Input: a = [1, 3, 8], x = 5
Output: bisect_left = bisect_right = 2

Constraints

a is sorted in non-decreasing order.
Both return values are in [0, n].

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Linear scan	`O(n)`	`O(1)`
Optimal (half-open binary search)	`O(log n)`	`O(1)`

1Linear scan

TimeO(n)

SpaceO(1)

Walk until the first element that is >= x (left) or > x (right).

i = 0; while i < n and a[i] < x: i++ (left).
Use <= for the right version.

Java

class Solution {
    static int bisectLeft(int[] a, int x) {
        int i = 0;
        while (i < a.length && a[i] < x) i++;
        return i;
    }

    static int bisectRight(int[] a, int x) {
        int i = 0;
        while (i < a.length && a[i] <= x) i++;
        return i;
    }
}

2Optimal (half-open binary search)

TimeO(log n)

SpaceO(1)

Search over [0, n). For bisect_left, move hi = mid whenever a[mid] >= x, otherwise lo = mid + 1. For bisect_right, use a[mid] > x. When lo == hi, that is the boundary. These two functions answer insert position, floor, ceil, first/last occurrence and count.

lo = 0, hi = n.
While lo < hi: mid; if condition(mid) hi = mid else lo = mid + 1.
Return lo.

Java

class Solution {
    static int bisectLeft(int[] a, int x) {
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] >= x) hi = mid; else lo = mid + 1;
        }
        return lo;
    }

    static int bisectRight(int[] a, int x) {
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] > x) hi = mid; else lo = mid + 1;
        }
        return lo;
    }
}

Edge cases to test

x smaller than every element (0)
x larger than every element (n)
x not present (both equal)

Hints

Hint 1

bisect_left: first index with a[i] >= x. bisect_right: first index with a[i] > x. Only the comparison differs.

FAQ

What is the best time complexity for bisect_left, bisect_right?

Optimal (half-open binary search) runs in O(log n) time and O(1) extra space.

Which pattern does bisect_left, bisect_right use?

It is a binary search problem that uses the bisect pattern. Other problems with the same pattern: Search Insert Position, Floor in a Sorted Array, Ceil in a Sorted Array.

Is there a brute force solution for bisect_left, bisect_right?

Yes. Linear scan takes O(n) time and O(1) space. Walk until the first element that is = x (left) or x (right).

Which edge cases should I test for bisect_left, bisect_right?

x smaller than every element (0); x larger than every element (n); x not present (both equal).