Binary Search
Given a sorted array of integers, find the index of a target value using binary search.
Constraints:
- The input array is sorted in ascending order
- The target value is an integer
Examples:
Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Explanation: The target value 9 is at index 4 in the sorted array.
Solutions
Binary Search
Time: O(log n)Space: O(1)
The binary search algorithm works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, the next interval will be the lower half. Otherwise, the next interval will be the upper half. The process is repeated until the size of the interval is zero, at which point the target value is either found or determined to be not in the array.
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1;
}Follow-up:
What if the input array is not sorted?
