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.
| Problems | 10, easy to hard |
|---|---|
| Languages | Python and Java |
| Forms | Boundaries, 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++.
- Exact match: closed interval.
- First true or lower bound: half-open, hi = mid when the condition holds.
- Rotated arrays: compare against an end to find the sorted half.
- Search on the answer: monotonic yes/no check, then find the smallest or largest feasible value.
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 Classic binary search: return the index of a target in a sorted array, or -1.
easyKeep 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.
pythondef 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 -1javaimport 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 Integer square root: the floor of sqrt(x) without using a library function.
easyBinary 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.
pythondef 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 ansjavaimport 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 First and last position of a target in a sorted array with duplicates.
mediumWrite 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.
pythondef 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]javaimport 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 Search in a rotated sorted array of distinct values.
mediumAt 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).
pythondef 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 -1javaimport 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 Find the minimum element in a rotated sorted array.
mediumCompare 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.
pythondef 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]javaimport 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 Find a peak element: an index whose value is greater than its neighbours.
mediumIf 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).
pythondef 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 lojavaimport 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 Koko eating bananas: the smallest eating speed that finishes all piles within h hours.
mediumThe 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.
pythondef 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 lojavaimport 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 Capacity to ship packages within D days, keeping the packages in order.
hardThe 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.
pythondef 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 lojavaimport 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 Aggressive cows: place k cows in stalls to maximise the minimum distance between any two.
hardSort 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.
pythondef 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 ansjavaimport 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 Median of two sorted arrays in O(log(min(m, n))).
hardBinary 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.
pythondef 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 + 1javaimport 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
- Sorting algorithm interview questions with worked solutions
- Two pointers interview questions with worked solutions
- Array interview questions with worked solutions
- Greedy algorithm interview questions with worked solutions
- Top K elements interview questions with worked solutions
- Matrix interview questions with worked solutions
More in DSA Interview Questions
- Binary Search Tree Interview Questions and Answers
- Binary Tree Interview Questions and Answers
- Bit manipulation interview questions with worked solutions
- Bitmask DP Interview Questions
- Cyclic sort pattern interview questions with worked solutions
- DFS (Depth-First Search) Interview Questions
- Dijkstra and Shortest Path Interview Questions
- Divide and Conquer Interview Questions
- Dynamic Programming Interview Questions
- Edit Distance and String DP Interview Questions
- Fast and slow pointers interview questions with solutions
- Fenwick Tree (Binary Indexed Tree) Interview Questions