Binary Search
EasyGiven an array of integers nums
which is sorted in ascending order, and an integer target,
write a function to search target
in nums.
If target
exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
Example
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4.
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1.
Explanation
Binary search is a divide and conquer algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array and eliminates half of the search space with each iteration.
The key insight is that because the array is sorted, we can determine which half the target must be in (if it exists) by comparing it to the middle element.
We maintain two pointers: left
and right,
representing the current search range. In each iteration:
- Calculate
mid = left + (right - left) / 2to avoid integer overflow - Compare
nums[mid]withtarget - If equal, return
mid - If
nums[mid] < target, search right half (left = mid + 1) - If
nums[mid] > target, search left half (right = mid - 1) - If
left > right, target doesn't exist, return-1
Idea Map
Initialize left = 0, right = len(nums) - 1
While left <= right
1. mid = left + (right-left)/2
2. If nums[mid] == target: Return mid
3. If nums[mid] < target: left = mid + 1
4. Else: right = mid - 1
After loop: Return -1 (not found)
Complexity Analysis
Time Complexity
O(log n) - We eliminate half of the remaining elements with each iteration.
Space Complexity
O(1) - We only use a constant amount of extra space for pointers.
Code
def search(nums, target):
Initializes the function `search` which takes the sorted array `nums` and the `target` value as input.
left, right = 0, len(nums) - 1
Initializes two pointers: `left` at start (0) and `right` at end (last index) of the array.
while left <= right:
Loop continues while there's a valid search range (left pointer hasn't passed right pointer).
mid = left + (right - left) // 2
Calculates middle index using this formula to prevent integer overflow (unlike (left + right) // 2).
if nums[mid] == target:
Checks if the middle element equals our target value.
return mid
Target found! Return the index where it's located.
elif nums[mid] < target:
If middle element is less than target, the target must be in the right half (array is sorted).
left = mid + 1
Move left pointer to mid + 1, discarding the left half including mid.
else:
Otherwise, middle element is greater than target, so target must be in the left half.
right = mid - 1
Move right pointer to mid - 1, discarding the right half including mid.
return -1
Target not found in array, return -1.
public int search(int[] nums, int target) {
Initializes the function `search` which takes the integer array `nums` and the `target` value as input.
int left = 0, right = nums.length - 1;
Initializes two pointers: `left` at start (0) and `right` at end (last index) of the array.
while (left <= right) {
Loop continues while there's a valid search range (left pointer hasn't passed right pointer).
int mid = left + (right - left) / 2;
Calculates middle index using this formula to prevent integer overflow (unlike (left + right) / 2).
if (nums[mid] == target) {
Checks if the middle element equals our target value.
return mid;
Target found! Return the index where it's located.
} else if (nums[mid] < target) {
If middle element is less than target, the target must be in the right half (array is sorted).
left = mid + 1;
Move left pointer to mid + 1, discarding the left half including mid.
} else {
Otherwise, middle element is greater than target, so target must be in the left half.
right = mid - 1;
Move right pointer to mid - 1, discarding the right half including mid.
}
End of the if-else chain.
}
End of the while loop.
return -1;
Target not found in array, return -1.
}
End of the function.
int search(vector<int>& nums, int target) {
Initializes the function `search` which takes a reference to the vector `nums` and the `target` value as input.
int left = 0, right = nums.size() - 1;
Initializes two pointers: `left` at start (0) and `right` at end (last index) of the vector.
while (left <= right) {
Loop continues while there's a valid search range (left pointer hasn't passed right pointer).
int mid = left + (right - left) / 2;
Calculates middle index using this formula to prevent integer overflow (unlike (left + right) / 2).
if (nums[mid] == target) {
Checks if the middle element equals our target value.
return mid;
Target found! Return the index where it's located.
} else if (nums[mid] < target) {
If middle element is less than target, the target must be in the right half (array is sorted).
left = mid + 1;
Move left pointer to mid + 1, discarding the left half including mid.
} else {
Otherwise, middle element is greater than target, so target must be in the left half.
right = mid - 1;
Move right pointer to mid - 1, discarding the right half including mid.
}
End of the if-else chain.
}
End of the while loop.
return -1;
Target not found in vector, return -1.
}
End of the function.
Edge Cases & Common Mistakes
Integer overflow when calculating mid
Always use left + (right - left) / 2 instead of (left + right) / 2 to prevent overflow with large indices.
Infinite loop with wrong pointer updates
Make sure to use mid + 1 and mid - 1, not just mid. Otherwise, you'll get stuck checking the same element repeatedly.
Empty or single-element arrays
The algorithm handles these correctly. For empty arrays, the loop doesn't execute and returns -1. For single elements, it checks that element directly.
Related Problems
What is Binary Search?
Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.
Learn more about binary search →Disclaimer: This problem is for educational purposes. Practice the 'Binary Search' problem on LeetCode.