NeetCode 150 · Binary Search

Binary Search Problems

Binary search isn't just for sorted arrays — it applies to any monotonic function. 'Binary search on the answer' is a powerful technique for optimization problems.

Problems: 7
Easy: 1
Medium: 5
Hard: 1
Learning approach: Read the problem. Try the test cases yourself first. Click Hint if stuck — it guides without spoiling. Use Show Solution only after a genuine attempt. Then hit Let's Code to run your solution live.
01 Easy ArrayBinary Search
Given sorted integer array nums and integer target, return the index of target, or -1 if not found. Must run in O(log n).
Test Cases
search([-1,0,3,5,9,12], 9) → 4 search([-1,0,3,5,9,12], 2) → -1
left/right pointersmid = (l+r)//2O(log n)
Maintain left and right boundaries. Compare the middle element to target and eliminate half the array each step.
Python Solution
def search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1
Key idea: Classic binary search. The invariant: if target exists, it's always in [left, right]. Each iteration halves the search space.
Time: O(log n).
Space: O(1).
02 Medium ArrayBinary SearchMatrix
Given m×n matrix where rows are sorted and the first integer of each row is greater than the last of the previous row, search for a target value. Must run in O(log(m×n)).
Test Cases
searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3) → True searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 13) → False
virtual 1D indexdivmod for row/colO(log mn)
Treat the matrix as a virtual 1D sorted array. Map index i → row = i // cols, col = i % cols.
Python Solution
def searchMatrix(matrix, target): rows, cols = len(matrix), len(matrix[0]) left, right = 0, rows * cols - 1 while left <= right: mid = (left + right) // 2 r, c = divmod(mid, cols) val = matrix[r][c] if val == target: return True elif val < target: left = mid + 1 else: right = mid - 1 return False
Key idea: The matrix is effectively a sorted 1D array. Binary search on virtual index, convert to (row, col) with divmod. O(log(m×n)).
Time: O(log(m×n)).
Space: O(1).
03 Medium ArrayBinary Search
Koko can eat k bananas per hour from a pile. She has h hours. Find the minimum integer k such that she can finish all piles in h hours.
Test Cases
minEatingSpeed([3,6,7,11], 8) → 4 minEatingSpeed([30,11,23,4,20], 5) → 30 minEatingSpeed([30,11,23,4,20], 6) → 23
binary search on answerceil divisionmonotonic feasibility
Is there a monotonic relationship between speed k and feasibility? If k works, does k+1 also work?
Python Solution
import math def minEatingSpeed(piles, h): left, right = 1, max(piles) while left < right: mid = (left + right) // 2 hours = sum(math.ceil(p / mid) for p in piles) if hours <= h: right = mid # mid is feasible, try lower else: left = mid + 1 # too slow, need faster return left
Key idea: Binary search on the answer (speed k). The feasibility function is monotonic: if k works, anything larger also works. Find the smallest feasible k.
Time: O(n log max(piles)).
Space: O(1).
04 Medium ArrayBinary Search
Given sorted array rotated at some unknown pivot, find the minimum element. Must run in O(log n).
Test Cases
findMin([3,4,5,1,2]) → 1 findMin([4,5,6,7,0,1,2]) → 0 findMin([11,13,15,17]) → 11
rotated array logicnums[mid] vs nums[right]O(log n)
Compare mid to the right boundary. If mid > right, the minimum is in the right half. Otherwise it's in the left half (including mid).
Python Solution
def findMin(nums): left, right = 0, len(nums) - 1 while left < right: mid = (left + right) // 2 if nums[mid] > nums[right]: left = mid + 1 # min is in the right portion else: right = mid # min is in the left portion (mid could be min) return nums[left]
Key idea: Compare mid to the rightmost element. If mid > right, the array is not sorted in [mid, right] — min must be to the right of mid. Otherwise, min is in [left, mid].
Time: O(log n).
Space: O(1).
05 Medium ArrayBinary Search
Given sorted array rotated at some pivot, search for target. Return index or -1. Must run in O(log n). No duplicates.
Test Cases
search([4,5,6,7,0,1,2], 0) → 4 search([4,5,6,7,0,1,2], 3) → -1 search([1], 0) → -1
determine sorted halftwo-case logicO(log n)
At any mid point, one half is guaranteed to be sorted. Determine which half is sorted, then check if target falls in it.
Python Solution
def search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid # Left half is sorted if nums[left] <= nums[mid]: if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 # Right half is sorted else: if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1 return -1
Key idea: In a rotated array, at least one half around mid is always sorted. Check which half is sorted, then decide which half contains the target.
Time: O(log n).
Space: O(1).
06 Medium Hash MapBinary SearchDesign
Design a data structure that stores key-value pairs with timestamps. set(key, value, timestamp) stores the value; get(key, timestamp) returns the value with the largest timestamp ≤ given timestamp.
Test Cases
t = TimeMap() t.set('foo', 'bar', 1) t.get('foo', 1) → 'bar' t.get('foo', 3) → 'bar' t.set('foo', 'bar2', 4) t.get('foo', 4) → 'bar2'
defaultdict of listbisect_rightbinary search on timestamps
Store (timestamp, value) pairs sorted by timestamp. For get, binary search for the largest timestamp ≤ given.
Python Solution
from collections import defaultdict import bisect class TimeMap: def __init__(self): self.store = defaultdict(list) # key → [(timestamp, value)] def set(self, key, value, timestamp): self.store[key].append((timestamp, value)) def get(self, key, timestamp): if key not in self.store: return "" pairs = self.store[key] # Find rightmost timestamp <= given timestamp idx = bisect.bisect_right(pairs, (timestamp, chr(127))) - 1 return pairs[idx][1] if idx >= 0 else ""
Key idea: set appends in order (timestamps are strictly increasing). get uses binary search to find the largest stored timestamp ≤ query. bisect_right finds the insertion point just past the target.
Time: O(1) set, O(log n) get.
Space: O(n).
07 Hard ArrayBinary SearchDivide and Conquer
Given two sorted arrays nums1 and nums2, find the median of the two sorted arrays. Must run in O(log(m+n)).
Test Cases
findMedianSortedArrays([1,3], [2]) → 2.0 findMedianSortedArrays([1,2], [3,4]) → 2.5
binary search on partitionensure nums1 shorterO(log min(m,n))
Binary search on the partition of nums1. For the partition to be correct, the max of the left sides must be ≤ min of the right sides.
Python Solution
def findMedianSortedArrays(nums1, nums2): # Ensure nums1 is the shorter array if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1 m, n = len(nums1), len(nums2) half = (m + n) // 2 left, right = 0, m while True: i = (left + right) // 2 # partition index for nums1 j = half - i # partition index for nums2 l1 = nums1[i-1] if i > 0 else float('-inf') r1 = nums1[i] if i < m else float('inf') l2 = nums2[j-1] if j > 0 else float('-inf') r2 = nums2[j] if j < n else float('inf') if l1 <= r2 and l2 <= r1: if (m + n) % 2 == 1: return float(min(r1, r2)) return (max(l1, l2) + min(r1, r2)) / 2.0 elif l1 > r2: right = i - 1 else: left = i + 1
Key idea: Binary search on the partition of the shorter array. Find the partition where left halves of both arrays together have exactly half the total elements, with max(left) ≤ min(right).
Time: O(log min(m,n)).
Space: O(1).
← Prev Category Next Category →