Binary Search
Given a sorted array of integers `nums` and an integer `target`, return the index of `target` in the array, or `-1` if it is not present. The solution must run in O(log n) time. **Core Insight:** Because the array is sorted, we can eliminate half the search space with every comparison. We maintain two pointers `left` and `right`. At each step we compute `mid = (left + right) / 2`. If `nums[mid] == target` we return `mid`. If `nums[mid] < target` the answer must be in the right half, so we set `left = mid + 1`. Otherwise it is in the left half, so we set `right = mid - 1`. **Algorithm:** Classic binary search. Loop while `left <= right`. Compute mid, compare, and narrow the window. Return -1 if the loop ends without finding the target. **Watch out:** Use `mid = left + (right - left) / 2` instead of `(left + right) / 2` to avoid integer overflow in languages with fixed-width integers. **Complexity:** Time O(log n) — the window halves each iteration. Space O(1) — no extra memory.
Constraints
- •
1 ≤ nums.length ≤ 10⁴ - •
All integers in nums are unique - •
nums is sorted in ascending order
def search(nums: list[int], target: int) -> int:
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