0704.Binary_Search

• Link: 704. Binary Search - Easy
• Track: NeetCode150

Question

Restate the problem

• Given a sorted array nums and a target, return its index. Return -1 if not found.

Edge Case

• Empty array → return -1
• Target smaller than nums[0] or larger than nums[-1] → return -1

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Binary Search	$O(\log n)$	$O(1)$

Method 1 - Binary Search

Approach

Key Insight

Sorted array → each step, compare nums[mid] to target and eliminate half the remaining search space.

• nums[mid] < target → target is in right half → left = mid + 1
• nums[mid] > target → target is in left half → right = mid - 1

Step-by-step:

1. Set left = 0, right = len(nums) - 1.
2. While left <= right:
   • Compute mid = left + (right - left) // 2
   • If nums[mid] == target → return mid
   • If nums[mid] < target → left = mid + 1
   • Else → right = mid - 1
3. Return -1.

Complexity

• Time Complexity: $O(\log n)$
• Space Complexity: $O(1)$

Code

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
 
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
 
        return -1

---

Mistake

• left < right instead of left <= right: misses the case where the answer is the single remaining element.
• right = mid instead of right = mid - 1: causes infinite loop when left == mid.
• mid = (left + right) // 2: integer overflow in other languages; prefer left + (right - left) // 2.