The challenge
Return the index of a target in an ascending sorted array, or −1 if it is absent.
Values are distinct. Empty input returns −1. Indices are zero-based.
Example
[−1, 0, 3, 5, 9, 12, 15, 18], target = 9 → 4.
Use the walkthrough below to inspect the input and each state change.
See Exact search, step by step
Inspect the comparison, the invariant, and the next boundary.
Inclusive candidate indicestarget = 9
Current comparisonResolved positionNumbers below = indices
- Left
- 0
- Middle
- —
- Right
- 7
Step 01 / 5
Start with the candidate indices
The retained interval contains the answer whenever it exists. Watch why each comparison can discard one side.
left = 0; right = 7Recorded result so far
Not resolved
View exact input
Input: [-1,0,3,5,9,12,15,18] · target = 9
Put it into code
Keep an inclusive interval [left, right]. A comparison with the middle eliminates every value on one side.
Indices are zero-based. C++ uses C++17 or later.
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 -1#include <vector>
int binary_search(const std::vector<int>& nums, int target) {
int left = 0, right = static_cast<int>(nums.size()) - 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;
}