Implementing classic binary search. Binary search is an $O(log N)$ algorithm to locate a target element within a sorted array.
Algorithm Details
We maintain two boundary markers: low and high. In each iteration, we select the midpoint index: mid = low + (high - low) / 2. We use this division formula instead of (low + high) / 2 to prevent potential integer overflow bugs in languages like C++ and Java.
C++ Implementation
int binarySearch(vector &nums, int target) {
int low = 0, high = nums.size() - 1;
while( low <= high ){
int mid = low + (high - low) / 2;
if( nums[mid] == target )
return mid;
else if( nums[mid] < target )
low = mid + 1; // Narrow search to upper half
else
high = mid - 1; // Narrow search to lower half
}
return -1; // Target not found
}
Complexity
- Time Complexity: $O(log N)$ since we halve the search space in each step.
- Space Complexity: $O(1)$ constant space complexity.