Binary Search

Problem

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 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.

Solution

Approach: Classic Binary Search

The key insight is to repeatedly divide the search space in half. Compare the middle element with the target and eliminate half of the remaining elements based on the comparison.

Algorithm:

Set left pointer to 0 and right pointer to end of array
While left <= right:
- Calculate middle index
- If middle element equals target, return index
- If middle element is less than target, search right half
- If middle element is greater than target, search left half
If not found, return -1

Implementation

class Solution:
    def search(self, 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

Alternative (Avoiding Integer Overflow):

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            # Avoid potential overflow: (left + right) // 2
            mid = left + (right - left) // 2

            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1

Complexity Analysis

Time Complexity: O(log n), where n is the length of the array. We halve the search space with each iteration.
Space Complexity: O(1), we only use a constant amount of extra space.

Key Insights

Halving Search Space: Binary search is efficient because it eliminates half of the remaining elements with each comparison, giving us logarithmic time complexity.
Sorted Array Required: Binary search only works on sorted arrays. The sorted property allows us to make decisions about which half to search based on comparisons.
Loop Invariant: The target, if it exists, is always within the range [left, right]. We maintain this invariant throughout the algorithm.
Overflow Prevention: Using left + (right - left) // 2 instead of (left + right) // 2 prevents potential integer overflow in languages where this is a concern (less relevant in Python).
Termination Condition: The loop continues while left <= right. When left > right, we’ve exhausted the search space without finding the target.