Binary Search

LeetCode 704: Binary Search Solution & Explanation

Problem Overview

TL;DR: The optimal solution leverages the sorted property of the array to repeatedly halve the search space by comparing the middle element to the target, achieving logarithmic time complexity.

The problem asks us to determine the index of a specific integer target within a sorted array of unique integers called nums. If the target is present, we return its index; otherwise, we return -1. This is the canonical definition of the LeetCode 704 problem, serving as the foundational example for the Binary Search algorithm. The constraints explicitly mandate an algorithm with O(log n) runtime complexity, ruling out linear scanning methods.

Brute Force Approach for Binary Search

The most intuitive way to search for an element in an array is to check every single element one by one. This is known as a linear search.

Pseudo-code:

function bruteForce(nums, target):
    for index from 0 to length of nums - 1:
        if nums[index] equals target:
            return index
    return -1

Time Complexity Analysis: The time complexity of this approach is O(n), where n is the number of elements in nums. In the worst-case scenario (target is at the end or not present), the algorithm must visit every element.

Why it fails: While this approach yields the correct result, the problem description explicitly requires an O(log n) runtime complexity. An O(n) solution is exponentially slower than O(log n) for large inputs. In a rigorous interview setting or against strict time limits, the brute force approach is considered incorrect because it fails to utilize the critical property that nums is sorted.

Algorithm Strategy: Binary Search Patterns

We implement the Binary Search - On Sorted Array/List subpattern using an iterative approach with two pointers.

1. Initialization: Define two pointers, left at index 0 and right at index n - 1. These pointers represent the inclusive bounds of the current search interval [left, right].
2. Iteration: Enter a loop that continues as long as left <= right. This condition ensures we process valid intervals, including the case where the interval contains a single element (where left == right).
3. Midpoint Calculation: Calculate the middle index mid. To avoid potential integer overflow with large indices, use the formula left + (right - left) / 2 rather than (left + right) / 2.
4. Comparison and Adjustment:
   • Check if nums[mid] equals target. If yes, return mid immediately.
   • If nums[mid] < target, the target must be in the right half. Move the left pointer to mid + 1.
   • If nums[mid] > target, the target must be in the left half. Move the right pointer to mid - 1.
5. Termination: If the loop finishes without returning, the target is not in the array. Return -1.

Execution Flow

Let's trace the algorithm with nums = [-1, 0, 3, 5, 9, 12] and target = 9.

1. Start: left = 0, right = 5. Search space is indices [0, 5].
2. Iteration 1:
   • left <= right (0 <= 5) is true.
   • Calculate mid: 0 + (5 - 0) / 2 = 2.
   • nums[2] is 3.
   • Compare 3 with target (9). Since 3 < 9, target is in the right half.
   • Update left to mid + 1 = 3.
   • New search space: indices [3, 5].
3. Iteration 2:
   • left <= right (3 <= 5) is true.
   • Calculate mid: 3 + (5 - 3) / 2 = 4.
   • nums[4] is 9.
   • Compare 9 with target (9). They are equal.
   • Return: 4.

Proof of Correctness

The correctness of this algorithm relies on the invariant that if the target exists in the array, it must be located within the current interval [left, right].

1. Initialization: At the start, the interval is the entire array [0, n-1]. If the target exists, it is trivially within this range.
2. Maintenance: In each step, we compare target with nums[mid].
   • If nums[mid] < target, then for all i <= mid, nums[i] < target (due to sorting). Thus, the target cannot be in [left, mid]. By setting left = mid + 1, we preserve the invariant that the target is in the new range [mid + 1, right].
   • If nums[mid] > target, then for all i >= mid, nums[i] > target. The target cannot be in [mid, right]. By setting right = mid - 1, we preserve the invariant for the new range [left, mid - 1].
3. Termination: The loop terminates when left > right. This implies the search interval is empty. Since the invariant guarantees the target would be in the interval if it existed, an empty interval proves the target is not present in the array.

Pattern Reuse Notes

The Binary Search - On Sorted Array/List pattern is highly versatile. Understanding the logic in LeetCode 704 allows you to solve several related problems:

• LeetCode 35: Search Insert Position: Instead of returning -1 when the target isn't found, you return left, which represents the index where the target should be inserted to maintain order.
• LeetCode 69: Sqrt(x): Applies binary search on the answer space (integers from 0 to x) rather than an array, but the halving logic is identical.
• LeetCode 74: Search a 2D Matrix: Treats a sorted 2D matrix as a flattened sorted 1D array, applying the same binary search coordinate mapping.
• LeetCode 278: First Bad Version: A variation where you search for the first occurrence of a condition (true/false) rather than a specific number, using the same boundary reduction strategy.

Reference Implementation

C++ Solution for LeetCode 704

1class Solution {
2public:
3    int search(vector<int>& nums, int target) {
4        int left = 0;
5        int right = nums.size() - 1;
6
7        while (left <= right) {
8            // Prevent potential integer overflow
9            int mid = left + (right - left) / 2;
10
11            if (nums[mid] == target) {
12                return mid;
13            } else if (nums[mid] < target) {
14                // Target is in the right half
15                left = mid + 1;
16            } else {
17                // Target is in the left half
18                right = mid - 1;
19            }
20        }
21
22        return -1;
23    }
24};

Java Solution for LeetCode 704

1class Solution {
2    public int search(int[] nums, int target) {
3        int left = 0;
4        int right = nums.length - 1;
5
6        while (left <= right) {
7            // Calculate mid to avoid overflow
8            int mid = left + (right - left) / 2;
9
10            if (nums[mid] == target) {
11                return mid;
12            } else if (nums[mid] < target) {
13                // Target is in the upper half
14                left = mid + 1;
15            } else {
16                // Target is in the lower half
17                right = mid - 1;
18            }
19        }
20
21        return -1;
22    }
23}

Python Solution for LeetCode 704

1class Solution:
2    def search(self, nums: List[int], target: int) -> int:
3        left = 0
4        right = len(nums) - 1
5        
6        while left <= right:
7            # Integer division in Python
8            mid = left + (right - left) // 2
9            
10            if nums[mid] == target:
11                return mid
12            elif nums[mid] < target:
13                # Target must be to the right
14                left = mid + 1
15            else:
16                # Target must be to the left
17                right = mid - 1
18                
19        return -1