Autocoder

Binary search interview questions with worked solutions

Last updated 2026-11-19

Binary search halves the search space each step, so a sorted array of a billion items needs about 30 comparisons. In interviews it appears in three forms: finding a value or boundary in a sorted array, searching a partly sorted structure such as a rotated array, and "search on the answer", where you binary search a numeric range and test each candidate with a feasibility check.

The code is short, which is why the bugs are subtle: an off-by-one in the loop condition, an infinite loop from a mid that never moves, or overflow in (lo + hi) / 2. The problems below are written with explicit invariants so you can reason about them. Pair this page with sorting algorithms questions and the DSA coding round guide.

Problems10, easy to hard
LanguagesPython and Java
FormsBoundaries, rotated arrays, search on the answer

Pick one loop style and keep it

Style A, closed interval: lo = 0, hi = n - 1, loop while lo <= hi, move lo = mid + 1 or hi = mid - 1. Good for exact matches. Style B, half-open: hi = n, loop while lo < hi, and either lo = mid + 1 or hi = mid. Good for boundaries such as the first element that satisfies a condition.

Compute mid as lo + (hi - lo) / 2 to avoid integer overflow in Java and C++.

How to spot search on the answer

The statement asks for the minimum or maximum value of something, there is a simple check "is value x enough?", and the check is monotonic: once x works, every larger x also works (or the reverse). Capacity, speed, distance and time limits are typical.

Binary search interview questions with worked solutions: questions with worked answers

  1. 1

    Classic binary search: return the index of a target in a sorted array, or -1.

    easy

    Keep the search range [lo, hi]. Compare the middle element with the target and discard the half that cannot contain it. Stop when the range is empty. Time O(log n), space O(1).. Edge cases: empty array, single element, target smaller or larger than everything.

    python
    def binary_search(a, target):
        lo, hi = 0, len(a) - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if a[mid] == target:
                return mid
            if a[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return -1
    java
    import java.util.*;
    
    class Solution {
        static int binarySearch(int[] a, int target) {
            int lo = 0, hi = a.length - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (a[mid] == target) return mid;
                if (a[mid] < target) lo = mid + 1;
                else hi = mid - 1;
            }
            return -1;
        }
    }
  2. 2

    Integer square root: the floor of sqrt(x) without using a library function.

    easy

    Binary search the answer between 0 and x. If mid * mid is at most x, mid is a candidate and a bigger root might exist, so move lo up; otherwise move hi down. Use a 64-bit product in Java since mid * mid can overflow int. Time O(log x), space O(1).. Edge cases: x = 0 and 1, perfect squares, x near the int maximum.

    python
    def my_sqrt(x):
        lo, hi, ans = 0, x, 0
        while lo <= hi:
            mid = (lo + hi) // 2
            if mid * mid <= x:
                ans = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return ans
    java
    import java.util.*;
    
    class Solution {
        static int mySqrt(int x) {
            long lo = 0, hi = x, ans = 0;
            while (lo <= hi) {
                long mid = (lo + hi) / 2;
                if (mid * mid <= x) { ans = mid; lo = mid + 1; }
                else hi = mid - 1;
            }
            return (int) ans;
        }
    }
  3. 3

    First and last position of a target in a sorted array with duplicates.

    medium

    Write one boundary function that returns the first index whose value is at least the target (or greater than it, for the right edge). The left edge is bound(target); the right edge is bound(target + 1) - 1 for integers. Check that the left edge actually holds the target. Time O(log n), space O(1).. Edge cases: target missing, all elements equal the target, target at either end.

    python
    def search_range(a, t):
        def lower(x):
            lo, hi = 0, len(a)
            while lo < hi:
                mid = (lo + hi) // 2
                if a[mid] < x:
                    lo = mid + 1
                else:
                    hi = mid
            return lo
        first = lower(t)
        if first == len(a) or a[first] != t:
            return [-1, -1]
        return [first, lower(t + 1) - 1]
    java
    import java.util.*;
    
    class Solution {
        static int[] searchRange(int[] a, int t) {
            int first = lower(a, t);
            if (first == a.length || a[first] != t) return new int[]{-1, -1};
            return new int[]{first, lower(a, t + 1) - 1};
        }
        static int lower(int[] a, int x) {
            int lo = 0, hi = a.length;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (a[mid] < x) lo = mid + 1;
                else hi = mid;
            }
            return lo;
        }
    }
  4. 4

    Search in a rotated sorted array of distinct values.

    medium

    At each step, one half around mid is sorted. If a[lo] <= a[mid], the left half is sorted: if the target lies within it, search there, else go right. Otherwise the right half is sorted and the same test applies. For [4,5,6,7,0,1,2] and target 0 the search ends at index 4. Time O(log n), space O(1).. Edge cases: not rotated, two elements, target absent. Duplicates break the sorted-half test and can degrade to O(n).

    python
    def search_rotated(a, t):
        lo, hi = 0, len(a) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if a[mid] == t:
                return mid
            if a[lo] <= a[mid]:
                if a[lo] <= t < a[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                if a[mid] < t <= a[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return -1
    java
    import java.util.*;
    
    class Solution {
        static int searchRotated(int[] a, int t) {
            int lo = 0, hi = a.length - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (a[mid] == t) return mid;
                if (a[lo] <= a[mid]) {
                    if (a[lo] <= t && t < a[mid]) hi = mid - 1;
                    else lo = mid + 1;
                } else {
                    if (a[mid] < t && t <= a[hi]) lo = mid + 1;
                    else hi = mid - 1;
                }
            }
            return -1;
        }
    }
  5. 5

    Find the minimum element in a rotated sorted array.

    medium

    Compare a[mid] with a[hi]. If a[mid] is larger, the minimum lies strictly to the right, so lo = mid + 1. Otherwise the minimum is at mid or to its left, so hi = mid. The loop ends with lo at the minimum. Time O(log n), space O(1).. Edge cases: array not rotated (answer is the first element), one element, two elements.

    python
    def find_min(a):
        lo, hi = 0, len(a) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] > a[hi]:
                lo = mid + 1
            else:
                hi = mid
        return a[lo]
    java
    import java.util.*;
    
    class Solution {
        static int findMin(int[] a) {
            int lo = 0, hi = a.length - 1;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (a[mid] > a[hi]) lo = mid + 1;
                else hi = mid;
            }
            return a[lo];
        }
    }
  6. 6

    Find a peak element: an index whose value is greater than its neighbours.

    medium

    If a[mid] < a[mid + 1], the slope rises to the right, so a peak exists there; set lo = mid + 1. Otherwise a peak exists at mid or to its left; set hi = mid. Neighbours outside the array count as minus infinity, so a peak always exists, even in a monotonic array. Time O(log n), space O(1).. Edge cases: single element, strictly increasing or decreasing arrays, several peaks (any is valid).

    python
    def find_peak(a):
        lo, hi = 0, len(a) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < a[mid + 1]:
                lo = mid + 1
            else:
                hi = mid
        return lo
    java
    import java.util.*;
    
    class Solution {
        static int findPeak(int[] a) {
            int lo = 0, hi = a.length - 1;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (a[mid] < a[mid + 1]) lo = mid + 1;
                else hi = mid;
            }
            return lo;
        }
    }
  7. 7

    Koko eating bananas: the smallest eating speed that finishes all piles within h hours.

    medium

    The speed is monotonic: if speed k finishes in time, any larger speed does too. Binary search k from 1 to the largest pile. For a candidate k, the hours needed are the sum of ceil(pile / k). If the hours fit within h, try smaller; else go larger. Time O(n log m) for m the largest pile, space O(1).. Edge cases: h equal to the number of piles (answer is the max pile), huge piles (use long for hours), one pile.

    python
    def min_eating_speed(piles, h):
        lo, hi = 1, max(piles)
        while lo < hi:
            mid = (lo + hi) // 2
            hours = sum((p + mid - 1) // mid for p in piles)
            if hours <= h:
                hi = mid
            else:
                lo = mid + 1
        return lo
    java
    import java.util.*;
    
    class Solution {
        static int minEatingSpeed(int[] piles, int h) {
            int lo = 1, hi = 0;
            for (int p : piles) hi = Math.max(hi, p);
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                long hours = 0;
                for (int p : piles) hours += (p + mid - 1) / mid;
                if (hours <= h) hi = mid;
                else lo = mid + 1;
            }
            return lo;
        }
    }
  8. 8

    Capacity to ship packages within D days, keeping the packages in order.

    hard

    The minimum capacity is the heaviest package; the maximum is the total weight. Binary search that range. For a capacity, simulate loading: start a new day whenever the next package would overflow. If days needed is at most D, the capacity works, so search lower. Time O(n log(sum)), space O(1).. Edge cases: D = 1 (answer is the total), D equal to the package count (heaviest package), one package.

    python
    def ship_within_days(w, days):
        lo, hi = max(w), sum(w)
        while lo < hi:
            cap = (lo + hi) // 2
            need, cur = 1, 0
            for x in w:
                if cur + x > cap:
                    need += 1
                    cur = 0
                cur += x
            if need <= days:
                hi = cap
            else:
                lo = cap + 1
        return lo
    java
    import java.util.*;
    
    class Solution {
        static int shipWithinDays(int[] w, int days) {
            int lo = 0, hi = 0;
            for (int x : w) { lo = Math.max(lo, x); hi += x; }
            while (lo < hi) {
                int cap = lo + (hi - lo) / 2;
                int need = 1, cur = 0;
                for (int x : w) {
                    if (cur + x > cap) { need++; cur = 0; }
                    cur += x;
                }
                if (need <= days) hi = cap;
                else lo = cap + 1;
            }
            return lo;
        }
    }
  9. 9

    Aggressive cows: place k cows in stalls to maximise the minimum distance between any two.

    hard

    Sort the stall positions. For a candidate distance d, greedily put the first cow at the first stall and each next cow at the first stall at least d away. If k cows fit, d is feasible and a larger d may be too, so search upwards. This is a maximise version of search on the answer. Time O(n log n + n log D) for D the position range, space O(1).. Edge cases: k = 2 (answer is the range), k equal to the number of stalls, duplicate positions.

    python
    def max_min_distance(pos, k):
        pos.sort()
        def ok(d):
            count, last = 1, pos[0]
            for p in pos[1:]:
                if p - last >= d:
                    count += 1
                    last = p
            return count >= k
        lo, hi, ans = 1, pos[-1] - pos[0], 0
        while lo <= hi:
            mid = (lo + hi) // 2
            if ok(mid):
                ans = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return ans
    java
    import java.util.*;
    
    class Solution {
        static int maxMinDistance(int[] pos, int k) {
            Arrays.sort(pos);
            int lo = 1, hi = pos[pos.length - 1] - pos[0], ans = 0;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                int count = 1, last = pos[0];
                for (int i = 1; i < pos.length; i++) {
                    if (pos[i] - last >= mid) { count++; last = pos[i]; }
                }
                if (count >= k) { ans = mid; lo = mid + 1; }
                else hi = mid - 1;
            }
            return ans;
        }
    }
  10. 10

    Median of two sorted arrays in O(log(min(m, n))).

    hard

    Binary search a partition of the shorter array A so that the left halves of A and B together hold half the elements and every left value is at most every right value. Test aLeft <= bRight and bLeft <= aRight. If aLeft is too big, move the cut left in A, else right. For odd total length the median is the max of the left side; for even it is the average of max-left and min-right. Use infinities for missing neighbours. Time O(log(min(m, n))), space O(1).. Edge cases: one array empty, unequal lengths, all elements of one array smaller than the other.

    python
    def find_median(A, B):
        if len(A) > len(B):
            A, B = B, A
        m, n = len(A), len(B)
        half = (m + n + 1) // 2
        lo, hi = 0, m
        inf = float('inf')
        while lo <= hi:
            i = (lo + hi) // 2
            j = half - i
            aL = A[i - 1] if i > 0 else -inf
            aR = A[i] if i < m else inf
            bL = B[j - 1] if j > 0 else -inf
            bR = B[j] if j < n else inf
            if aL <= bR and bL <= aR:
                if (m + n) % 2:
                    return max(aL, bL)
                return (max(aL, bL) + min(aR, bR)) / 2
            if aL > bR:
                hi = i - 1
            else:
                lo = i + 1
    java
    import java.util.*;
    
    class Solution {
        static double findMedian(int[] A, int[] B) {
            if (A.length > B.length) return findMedian(B, A);
            int m = A.length, n = B.length, half = (m + n + 1) / 2;
            int lo = 0, hi = m;
            while (lo <= hi) {
                int i = (lo + hi) / 2, j = half - i;
                int aL = i > 0 ? A[i - 1] : Integer.MIN_VALUE;
                int aR = i < m ? A[i] : Integer.MAX_VALUE;
                int bL = j > 0 ? B[j - 1] : Integer.MIN_VALUE;
                int bR = j < n ? B[j] : Integer.MAX_VALUE;
                if (aL <= bR && bL <= aR) {
                    if ((m + n) % 2 == 1) return Math.max(aL, bL);
                    return (Math.max(aL, bL) + (double) Math.min(aR, bR)) / 2.0;
                }
                if (aL > bR) hi = i - 1;
                else lo = i + 1;
            }
            return 0;
        }
    }

Frequently asked questions

How do I avoid infinite loops in binary search?

Make sure each iteration shrinks the range. With lo < hi and hi = mid, mid must be computed rounding down; with lo = mid + 1 the range shrinks every time. Test a two-element array.

What is search on the answer?

Binary search over a range of possible answers, using a yes/no feasibility check that is monotonic. Capacity, speed and distance problems are the classic cases.

Does binary search need a sorted array?

It needs a monotonic property, not necessarily a sorted array. Rotated arrays, peaks and feasibility checks all work because the condition splits the range cleanly.

Why is lo + (hi - lo) / 2 recommended?

(lo + hi) can overflow a 32-bit int when both are large. Python integers do not overflow, but the safe form is a good habit in Java and C++.

What should I practise next?

Try two pointers questions for sorted-array scans and greedy questions, which supply many feasibility checks.

Related guides

More in DSA Interview Questions

See all in this section