Binary Search: Practice Problems with Solutions
Welcome to the practice problems for binary search. If you need a refresher on the code, the code templates have the patterns in all 6 languages. Each problem below includes a hint, a visual walkthrough, and the full solution.
Recommended Study Order
The problems are ordered by difficulty, but the progression matters as much as the individual solutions.
- Binary Search teaches the core iterative loop in its purest form. Master this before adding any complexity.
- Search Insert Position introduces the lower-bound pattern where the loop condition changes from
<=to<. - First and Last Position shows how to refine a search after a match by continuing to scan in one direction.
- Search in Rotated Sorted Array adds the twist of identifying which half of a partially sorted array is searchable.
- Koko Eating Bananas shifts from searching an array to searching the space of possible answers using a feasibility predicate.
- Median of Two Sorted Arrays combines binary search with partitioning logic and is the hardest problem in the set.
Easy Problems
1. Binary Search
LeetCode 704 | Difficulty: Easy
Brief: Locate a target integer in a sorted array and return its index, or -1 if it does not exist.
Why this pattern: This is the textbook application. A sorted array and a target value are the exact conditions binary search was designed for.
Key Insight: The loop condition left <= right ensures the last remaining element is checked. Use left + (right - left) / 2 to avoid integer overflow.
Visual:
graph TD
Start[Start] --> Loop{"left <= right?"}
Loop -->|Yes| B[Calculate mid]
B --> C{"nums[mid] == target?"}
C -->|Yes| D[Return mid]
C -->|No| E{"nums[mid] < target?"}
E -->|Yes| F[left = mid + 1]
E -->|No| G[right = mid - 1]
F --> Loop
G --> Loop
Loop -->|No| End[Return -1]
Code:
function search(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}This is the most direct application of the standard template. Every line maps to the three-step process: calculate the midpoint, compare, and shrink.
2. Search Insert Position
LeetCode 35 | Difficulty: Easy
Brief: Return the index where a target exists in a sorted array, or the index where it would be inserted to maintain sorted order.
Why this pattern: This is a lower-bound binary search. Instead of checking for an exact match, you find the first position where the value is greater than or equal to the target.
Key Insight: Use while (left < right) with right = mid. When the loop exits, left is the insertion point. Using < instead of <= means the loop stops when one element remains, which is the answer.
Visual:
graph TD
Start[Start] --> Loop{"left < right?"}
Loop -->|Yes| B[Calculate mid]
B --> C{"nums[mid] < target?"}
C -->|Yes| D[left = mid + 1]
C -->|No| E[right = mid]
D --> Loop
E --> Loop
Loop -->|No| End[Return left]
Code:
function searchInsert(nums, target) {
let left = 0, right = nums.length;
while (left < right) {
let mid = left + Math.floor((right - left) / 2);
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}Note the differences from the standard template. The right boundary starts at nums.length instead of nums.length - 1 because the insertion point could be past the end of the array. The loop uses < instead of <=, and when nums[mid] >= target, right is set to mid instead of mid - 1. This is a common lower-bound pattern worth memorizing separately.
Medium Problems
3. First and Last Position of Element in Sorted Array
LeetCode 34 | Difficulty: Medium
Brief: Find the starting and ending indices of a target value in an array with duplicates. Return [-1, -1] if the target is not present.
Why this pattern: Exact-match binary search stops at the first match, but here you need the boundaries of a run of identical values. The trick is to keep searching after a match by narrowing the window toward the boundary you want.
Key Insight: Run binary search twice. For the first position, when nums[mid] == target, record the index and search left (right = mid - 1). For the last position, search right (left = mid + 1).
Visual:
graph TD
Start[Start Search] --> Found{"target found?"}
Found -->|Yes| Record[Record index]
Record --> First{"Searching First?"}
First -->|Yes| MoveLeft[right = mid - 1]
First -->|No| MoveRight[left = mid + 1]
MoveLeft --> Start
MoveRight --> Start
Found -->|No| Done[Return result]
Code:
function searchRange(nums, target) {
const findBound = (isFirst) => {
let left = 0, right = nums.length - 1, result = -1;
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) {
result = mid;
if (isFirst) right = mid - 1;
else left = mid + 1;
} else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return result;
};
return [findBound(true), findBound(false)];
}The critical detail is that after finding a match, the search does not stop. For the first occurrence, moving right past mid forces the next iteration to search the left half, where any earlier match would be found. The last recorded match becomes the result, so the final value of result is the outermost occurrence in the searched direction.
4. Search in Rotated Sorted Array
LeetCode 33 | Difficulty: Medium
Brief: Search for a target in a sorted array that has been rotated at an unknown pivot. The array contains no duplicates.
Why this pattern: The array is not fully sorted, but one half of every midpoint is always fully sorted. You leverage that sorted half to determine which side of the midpoint could contain the target.
Key Insight: Compare nums[left] to nums[mid] to determine which half is sorted. If the left half is sorted and the target falls within its range, search the left half. Otherwise, search the right half. If the left half is not sorted, the right half must be sorted by elimination.
Visual:
graph TD
Start[Calculate mid] --> Sorted{"nums[left] <= nums[mid]?"}
Sorted -->|Yes Left Sorted| RangeL{"target in left range?"}
Sorted -->|No Right Sorted| RangeR{"target in right range?"}
RangeL -->|Yes| D[right = mid - 1]
RangeL -->|No| E[left = mid + 1]
RangeR -->|Yes| G[left = mid + 1]
RangeR -->|No| H[right = mid - 1]
Code:
function search(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return mid;
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else {
if (target > nums[mid] && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}The key mental shift is that instead of comparing against the target alone, you first determine which half of the array is sorted. In a rotated array, at any midpoint either the left segment or the right segment must be in ascending order. If the sorted segment contains the target (based on a range comparison), you search within it. Otherwise, you search the other side.
5. Koko Eating Bananas
LeetCode 875 | Difficulty: Medium
Brief: Koko can eat speed bananas per hour. Each pile takes ceil(pile / speed) hours. Find the minimum integer speed that lets Koko finish all piles within h hours.
Why this pattern: This is binary search on answer, the most common advanced binary search variation. You are not searching the array. You are searching the space of possible speeds from 1 to the largest pile.
Key Insight: The feasibility function is monotonic. If speed K works, any speed larger than K also works. Binary search finds the smallest K where the predicate returns true.
Visual:
graph TD
A["Search speed from 1 to max(piles)"] --> B[Check mid speed]
B --> C{"Can eat all in h hours?"}
C -->|Yes| D[Try slower: right = mid - 1]
C -->|No| E[Try faster: left = mid + 1]
D --> F[Track result = min feasible]
E --> B
F --> B
Code:
function minEatingSpeed(piles, h) {
let left = 1, right = Math.max(...piles);
let result = right;
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
let hours = 0;
for (let p of piles) {
hours += Math.ceil(p / mid);
}
if (hours <= h) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}This is the template for binary search on answer. The search bounds are not array indices but the minimum and maximum possible answer values. The feasibility function runs in
result variable tracks the last feasible speed as the search narrows, so when the loop exits, result holds the minimum feasible answer.Hard Problems
6. Median of Two Sorted Arrays
LeetCode 4 | Difficulty: Hard
Brief: Find the median of two sorted arrays in
Why this pattern: Binary search does not directly find the median. Instead, it finds the correct partition point in the smaller array such that all elements on the left of both partitions are less than or equal to all elements on the right. This is binary search on partition positions.
Key Insight: If you partition both arrays at the right indices, the max of the left halves and the min of the right halves give you the median. Binary search on the smaller array to find the partition where the left-right condition holds.
Visual:
graph TD
A["Binary search on smaller array"] --> B["Partition the other array at (m+n+1)/2 - i"]
B --> C{"maxLeftA <= minRightB AND maxLeftB <= minRightA?"}
C -->|Yes| D[Compute median from partition edges]
C -->|No| E{"maxLeftA > minRightB?"}
E -->|Yes| F[Move partition left]
E -->|No| G[Move partition right]
F --> A
G --> A
Code:
function findMedianSortedArrays(nums1, nums2) {
if (nums1.length > nums2.length) {
[nums1, nums2] = [nums2, nums1];
}
let m = nums1.length, n = nums2.length;
let left = 0, right = m;
while (left <= right) {
let i = left + Math.floor((right - left) / 2);
let j = Math.floor((m + n + 1) / 2) - i;
let maxLeft1 = i === 0 ? -Infinity : nums1[i - 1];
let minRight1 = i === m ? Infinity : nums1[i];
let maxLeft2 = j === 0 ? -Infinity : nums2[j - 1];
let minRight2 = j === n ? Infinity : nums2[j];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
if ((m + n) % 2 === 0) {
return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
} else {
return Math.max(maxLeft1, maxLeft2);
}
} else if (maxLeft1 > minRight2) {
right = i - 1;
} else {
left = i + 1;
}
}
return 0;
}This is the hardest binary search problem partly because it is not immediately obvious that binary search applies. The key insight is that finding the median is equivalent to finding the correct partition of both arrays. By always binary searching the smaller array, each iteration runs in
These six problems cover the full range of binary search applications. Start with the classic sorted array search, work through boundary-finding and rotated arrays, move to binary search on answer with Koko, and finish with the partition-based median. By the end, you should be able to recognize when binary search applies even when the input does not look like a sorted array.