Binary Search (Classic Iterative)

Problem Statement

Given a sorted array nums and a target, return the index of target if it exists, otherwise return -1.

Example

Input:  nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: nums[4] == 9.

Approach

Keep a search window [left, right]. Look at the middle element: if it equals the target, return it; if it is too small, discard the left half; if it is too large, discard the right half. Each step halves the range.

Use mid = left + (right - left) / 2 to avoid integer overflow on very large indices.

Complexity

• Time: O(log n)
• Space: O(1)

Solution Code

Python

def binary_search(nums, target):
    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

Java

int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

C++

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Key Takeaways

• The array must be sorted for binary search to be valid.
• Prefer left + (right - left) / 2 over (left + right) / 2 to prevent overflow.
• Reference: LeetCode 704 (Binary Search); CLRS, Introduction to Algorithms, Ch. 2.