JuniorCodeVery commonNot answered yet
Implement binary search on a sorted array
Implement binary search on a sorted ascending array. Return the index of target, or -1 if it is absent.
Requirements:
- O(log n) time, O(1) extra space.
- Compute the midpoint as
low + (high - low) / 2to avoid integer overflow. - Get the loop boundary condition right; handle the empty array.
- Do not use
std::binary_searchorstd::lower_bound.
int binarySearch(const std::vector<int>& arr, int target) {
// your code here
}Write the implementation.
Binary search works on a sorted range by repeatedly halving the search space. Maintain low and high bounds; compare the middle element with the target; move the bound toward the target side. Time O(log n), space O(1).
- ✗Integer overflow in
mid = (low + high) / 2when low and high are large — uselow + (high - low) / 2 - ✗Off-by-one in loop condition:
while (low < high)vswhile (low <= high)changes semantics - ✗Not ensuring the input array is sorted — binary search on unsorted data gives wrong results
- →How does
std::lower_bounddiffer fromstd::binary_search? - →How would you extend binary search to find the leftmost / rightmost occurrence of a value?
Contents
Task
Implement binary search for a value in a sorted integer array. Return the index or -1 if not found.
Solution
#include <vector>
#include <cassert>
// Iterative binary search — O(log n) time, O(1) space
int binarySearch(const std::vector<int>& arr, int target) {
int low = 0;
int high = static_cast<int>(arr.size()) - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // safe midpoint
if (arr[mid] == target) return mid;
if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}
int main() {
std::vector<int> v = {1, 3, 5, 7, 9, 11, 13};
assert(binarySearch(v, 7) == 3);
assert(binarySearch(v, 1) == 0);
assert(binarySearch(v, 13) == 6);
assert(binarySearch(v, 4) == -1);
assert(binarySearch({}, 1) == -1);
}Key points
- Use
mid = low + (high - low) / 2, not(low + high) / 2, to avoid integer overflow. - Loop invariant:
low <= highmeans "there may still be an undiscovered element in the range". std::lower_boundfrom<algorithm>does the same but returns an iterator to the first element ≥ target.
Contents
