What is binary search?
Binary search is a fast way to find a value in a sorted array. It looks at the middle element, and if the target is smaller it searches the left half, otherwise the right half. Each step halves the search space, so it runs in O(log n) time. The array must be sorted for it to work.
- Binary search finds a value in a sorted array by repeatedly halving the search space.
- It runs in O(log n) time and O(1) extra space for the loop version.
- The array must be sorted first, and a safe midpoint is lo plus (hi minus lo) divided by 2.
How it works
Because the array is sorted, checking the middle tells you which half the target must be in. You throw away the other half every time, which is why it is so fast compared to scanning every element.
int binarySearch(vector<int>& arr, int target) {
int lo = 0, hi = arr.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
lo = mid + 1;
else
hi = mid - 1;
}
return -1; // not found
}int binarySearch(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
lo = mid + 1;
else
hi = mid - 1;
}
return -1; // not found
}def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1 # not foundKey points
- The array must be sorted first.
- Time complexity is O(log n) because the range halves each step.
- Space complexity is O(1) for the loop version.
A classic bug is computing the middle as (lo plus hi) divided by 2 in languages where that can overflow. Mentioning lo plus (hi minus lo) divided by 2 as the safe version shows attention to detail.
Frequently asked questions
Why must the array be sorted for binary search?
Binary search relies on comparing the middle element to decide which half to keep. That decision only works if the data is in order.
How do you find the first occurrence of a value?
Keep searching the left half even after a match instead of returning immediately, recording the index each time until the range closes.
Common follow up questions
Related interview questions
Want the full DSA guide?
Read every DSA concept with notes, diagrams, and code in one place. Track your progress as you go.
Open the DSA guide All DSA questions