704. Binary Search
Model: qwen2.5-coder:14b
Topics: Binary Search
FAANG asked: 1
Acceptance rate: 54.3%
Problem Breakdown
The problem requires us to search for a target integer in a sorted array of integers using binary search. The inputs are:
nums: An array of integers sorted in ascending order.target: An integer that we need to find in the array.
The output is:
- The index of the target if it exists in the array.
-1if the target does not exist in the array.
Implicit constraints and edge cases include:
- The array can be empty, in which case the function should return
-1. - All integers in the array are unique.
- The array length is between 1 and 10^4.
- The values of the integers range from -9999 to 9999.
Intuition
A brute-force approach would involve iterating through the entire array linearly to find the target, which would result in a time complexity of O(n). This is inefficient for large arrays. The key insight is that since the array is sorted, we can use binary search to reduce the time complexity to O(log n).
Binary search 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, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.
Approach
We will implement a binary search algorithm using two pointers: left and right, which represent the current search bounds within the array. The steps are as follows:
- Initialize
leftto 0 andrightto the last index of the array. - While
leftis less than or equal toright:- Calculate the middle index
midas(left + right) // 2. - If
nums[mid]equals the target, returnmid. - If
nums[mid]is less than the target, move theleftpointer tomid + 1. - If
nums[mid]is greater than the target, move therightpointer tomid - 1.
- Calculate the middle index
- If the loop exits without finding the target, return
-1.
Complexity Analysis
- Time Complexity: O(log n) because we are dividing the search space in half with each iteration.
- Space Complexity: O(1) because we are using a constant amount of extra space.
Solution
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Edge Cases Handled
- Empty Array: If the array is empty,
leftwill be greater thanrightinitially, and the function will return-1. - Target at Boundaries: The algorithm correctly handles cases where the target is the first or last element in the array.
- Target Not Present: If the target is not present, the loop will exhaust all possibilities, and the function will return
-1.