EasyBlind75ArrayBinary Search
Binary Search
Given a sorted array of integers nums and a target, search for the target. Return its index or -1.
Examples
Input
nums = [-1,0,3,5,9,12], target = 9
Output
4
9 exists in nums and its index is 4.
Input
nums = [-1,0,3,5,9,12], target = 2
Output
-1
2 does not exist in nums so return -1.
Constraints
- •
1 <= nums.length <= 10^4 - •
-10^4 < nums[i], target < 10^4 - •
All the integers in nums are unique. - •
nums is sorted in ascending order.
Approaches
Scan through the array to find the target.
CodeT: O(n) | S: O(1)
def search(nums, target):
for i in range(len(nums)):
if nums[i] == target:
return i
return -1Repeatedly divide the search interval in half.
CodeT: O(log n) | S: O(1)
def 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 -1Recursive implementation with same time complexity.
Diagram
nums=[-1,0,3,5,9,12], target=9
left=0,right=5,mid=2(3<9)->left=3
left=3,right=5,mid=4(9==9)->return 4
CodeT: O(log n) | S: O(log n)
def search(nums, target):
def bs(left, right):
if left > right:
return -1
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
return bs(mid + 1, right)
else:
return bs(left, mid - 1)
return bs(0, len(nums) - 1)Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Linear Search | O(n) | O(1) | Scan through the array to find the target. |
| Binary Search - Iterative | O(log n) | O(1) | Repeatedly divide the search interval in half. |
| Binary Search - Recursive | O(log n) | O(log n) | Recursive implementation with same time complexity. |
Linear Search
T: O(n)S: O(1)
Scan through the array to find the target.
Binary Search - Iterative
T: O(log n)S: O(1)
Repeatedly divide the search interval in half.
Binary Search - Recursive
T: O(log n)S: O(log n)
Recursive implementation with same time complexity.
Common Mistakes
Using (left + right) // 2 which can overflow for large values
Not using left <= right (off-by-one error)
Updating left to mid instead of mid + 1