LeetCode 704 - Binary Search

2026-07-03

easy　array　binary search

You are given an array of distinct integers nums, sorted in ascending order, and an integer target.

Implement a function to search for target within nums. If it exists, return its index; otherwise, return -1.

Your solution must run in O(log N) time.

Example 1:

Input: nums = [-1,0,2,4,6,8], target = 4

Output: 3

Example 2:

Input: nums = [-1,0,2,4,6,8], target = 3

Output: -1

Constraints:

• 1 <= nums.length <= 10,000
• -10,000 < nums[i], target < 10,000
• All integers in nums are unique.

Solution 1:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # Approach: Brute Force — Two-Pointer Inward Scan
        # 1. Start with one pointer at the left end and one at the right end.
        # 2. Check both ends on each iteration; if either matches, return its index.
        # 3. Move both pointers inward until they cross.
        # 4. If no match is found, return -1.
        # Time Complexity: O(N) — in the worst case, both pointers meet in the middle
        #   without finding the target.
        # Space Complexity: O(1).
        l_idx, r_idx = 0, len(nums) - 1

        while l_idx <= r_idx:
            if nums[l_idx] == target:
                return l_idx
            elif nums[r_idx] == target:
                return r_idx
            l_idx += 1
            r_idx -= 1
        return -1

Solution 2:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # Approach: Binary Search
        # Since the array is sorted, we can repeatedly halve the search space.
        # 1. Compute the midpoint of the current range.
        # 2. If nums[mid] == target, return mid.
        # 3. If nums[mid] > target, the target must be in the left half — move right pointer.
        # 4. If nums[mid] < target, the target must be in the right half — move left pointer.
        # 5. If the pointers cross without a match, the target is not in the array.
        # Time Complexity: O(log N) — the search space halves on every iteration.
        # Space Complexity: O(1).
        l_idx, r_idx = 0, len(nums) - 1
        while l_idx <= r_idx:
            middle = (l_idx + r_idx) // 2
            if nums[middle] > target:
                r_idx = middle - 1
            elif nums[middle] < target:
                l_idx = middle + 1
            else:
                return middle
        return -1

Conclusion

Today we solved Binary Search — the foundational algorithm behind an entire family of problems.

Solution 1 uses a two-pointer inward scan, checking both ends simultaneously. While it's slightly better than a naive left-to-right scan, it's still O(N) in the worst case — the target could be sitting right in the middle.

Solution 2 is true binary search. Because the array is sorted, we know immediately which half of the remaining range can possibly contain the target. Each comparison eliminates half the search space, giving O(log N) — for 10,000 elements, that's at most 14 comparisons instead of 10,000.

The two invariants to keep straight: use <= in the while condition (not <) so the single-element case is handled correctly, and shrink to mid - 1 / mid + 1 rather than mid itself to avoid an infinite loop when l_idx == r_idx.