Binary SearchEvidence Contributing
Binary Search (Classic Lookup)
Standard binary search over a sorted array (or a local monotonic comparison) to locate a target index or boundary.
Practice Problems: 7
Difficulty: 2 Easy·4 Medium·1 Hard
Core technique
Halve the search range each step by checking the middle element. Sorted order tells you which half cannot contain the target, so n elements take about log2 n comparisons.
How to recognize it
- The input is sorted, or some property flips from false to true at a single point.
- The problem asks for a target position, an insertion index, or the first or last position where something holds.
- The required time is O(log n), or n is large enough that a linear scan is too slow.
- You can tell which half to keep from the middle element alone.
Template
This is the closed-interval version. The search range is left to right inclusive, so the loop runs while left <= right and both bounds move past mid. Compute mid as left + (right - left) / 2 so the sum cannot overflow.
Python
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1Java
int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}JavaScript
function binarySearch(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const 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;
}Worked example: Search Insert Position
- For a strictly increasing array, return the target index or its insertion index. Use the same loop, but return left instead of -1 when it ends. With duplicates, this exact-match template is not a lower-bound search and may return any matching index.
- Take nums = 1, 3, 5, 6 and target = 2. Start with left = 0 and right = 3.
- mid = 1 holds 3, which is larger than 2, so right becomes 0.
- Now left = 0 and right = 0. mid = 0 holds 1, which is smaller than 2, so left becomes 1.
- left is greater than right, so the loop stops. left = 1 is exactly where 2 belongs.
- Why left is the insertion point: every index before left holds a value smaller than the target, and every index from left onward holds a larger one.
Complexity: O(log n) time and O(1) space.
Try Search Insert Position on LeetCodeCommon mistakes
- Writing left = mid or right = mid with a closed interval, which can loop forever. Move past mid with mid + 1 or mid - 1.
- Mixing conventions. With a half-open interval (right starts at n) the loop is left < right and right = mid. Pick one convention and keep the loop condition and both updates consistent with it.
- Computing mid as (left + right) / 2 in Java or C++, where the sum can overflow.
- Forgetting the empty array. right starts at -1, the loop never runs, and you must return the not-found value or insertion index 0.
- Running it on data that is not sorted. The result is silently wrong rather than an error.
When this pattern does not fit
- The data is unsorted and you only need one lookup. One linear scan costs less than sorting first.
- There is no monotonic property to split on, so the middle element tells you nothing about either half.
- You need membership checks across many lookups. A hash set gives O(1) lookups after a single build.