Difficulty: 🟢 Easy
Topics: Array, Binary Search

Solution

LeetCode 704, Binary Search

Problem Understanding

This problem gives us a sorted array of integers named nums and a target integer named target. The array is sorted in ascending order, meaning every element is smaller than the elements that come after it. We must determine whether the target value exists in the array. If it does, we return its index. If it does not, we return -1.

The important requirement is that the algorithm must run in O(log n) time complexity. This immediately rules out any solution that scans the array linearly from beginning to end, because a linear scan takes O(n) time in the worst case.

The input consists of:

nums, a sorted array of unique integers
target, the integer we want to locate

The output is:

The index of target if it exists in nums
-1 if the target does not exist

The constraints are small enough that many approaches would technically work, but the required logarithmic complexity strongly hints that the intended solution is binary search.

The constraints also guarantee several useful properties:

The array is already sorted
All values are unique
The array contains at least one element

Because the array is sorted and contains unique values, we can safely eliminate half of the remaining search space after every comparison.

Some important edge cases include arrays with a single element, targets smaller than the minimum element, targets larger than the maximum element, and targets that do not exist between valid values. A naive implementation can easily make off by one mistakes when updating boundaries, especially when only one or two elements remain.

Approaches

Brute Force Approach

The simplest solution is to iterate through the array from left to right and compare every element with the target.

If we find the target, we return its index immediately. If we reach the end of the array without finding it, we return -1.

This approach is correct because it checks every possible position where the target could appear. However, it is inefficient because in the worst case we may need to inspect all n elements.

Since the problem explicitly requires O(log n) runtime complexity, the brute force approach is not acceptable.

Optimal Approach, Binary Search

The key observation is that the array is sorted.

When we inspect the middle element:

If the middle element equals the target, we are done.
If the target is smaller than the middle element, the target can only exist in the left half.
If the target is larger than the middle element, the target can only exist in the right half.

Because we eliminate half of the remaining search space after every comparison, the runtime becomes logarithmic.

This repeated halving process is exactly what binary search is designed for.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Scan every element sequentially
Optimal	O(log n)	O(1)	Binary search repeatedly halves the search space

Algorithm Walkthrough

Initialize two pointers:

left = 0
right = len(nums) - 1

These pointers represent the current search range. 2. Continue searching while left <= right.

This condition means there is still at least one valid element left to examine. 3. Compute the middle index using:

mid = (left + right) // 2

The middle element divides the current search range into two halves. 4. Compare nums[mid] with target.

If they are equal, return mid because we found the target.
If target < nums[mid], move the right boundary:

right = mid - 1

The target must be in the left half.

Otherwise, move the left boundary:

left = mid + 1

The target must be in the right half. 5. If the loop finishes, the target does not exist in the array.

Return -1.

Why it works

The algorithm maintains the invariant that if the target exists, it must lie within the current range [left, right].

At every step, the middle element is checked. Because the array is sorted, one entire half of the search space can be safely discarded. The search interval becomes smaller and smaller until either the target is found or no valid range remains.

Since the range size is cut roughly in half each iteration, the algorithm completes in logarithmic time.

Python Solution

from typing import List

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

        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return mid

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

        return -1

The implementation begins by defining the search boundaries using left and right.

The while left <= right loop ensures that we continue searching as long as there is a valid interval remaining.

Inside the loop, we compute the middle index and compare the value at that position with the target.

If the middle value matches the target, we immediately return the index.

If the target is smaller, we shrink the search space by moving the right boundary leftward. If the target is larger, we move the left boundary rightward.

Eventually, either the target is found or the interval becomes empty. When the interval is empty, the target does not exist, so the function returns -1.

Go Solution

func search(nums []int, target int) int {
    left := 0
    right := len(nums) - 1

    for left <= right {
        mid := left + (right-left)/2

        if nums[mid] == target {
            return mid
        }

        if target < nums[mid] {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }

    return -1
}

The Go implementation follows the same logic as the Python solution.

One small difference is the middle index calculation:

mid := left + (right-left)/2

This form avoids potential integer overflow in languages where integers have fixed size. While overflow is not an issue for the given constraints, this is considered best practice in many binary search implementations.

Go slices are dynamic views over arrays, so we work directly with the slice nums. No additional memory allocation is required.

Worked Examples

Example 1

Input: nums = [-1,0,3,5,9,12], target = 9

Iteration	left	right	mid	nums[mid]	Action
1	0	5	2	3	Target is larger, move left to 3
2	3	5	4	9	Found target

The algorithm returns 4.

Example 2

Input: nums = [-1,0,3,5,9,12], target = 2

Iteration	left	right	mid	nums[mid]	Action
1	0	5	2	3	Target is smaller, move right to 1
2	0	1	0	-1	Target is larger, move left to 1
3	1	1	1	0	Target is larger, move left to 2

Now left = 2 and right = 1.

Since left > right, the search space is empty, so the algorithm returns -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	The search space is halved every iteration
Space	O(1)	Only a few variables are used

The runtime is logarithmic because each comparison removes half of the remaining elements from consideration. Starting with n elements, after one iteration only n/2 remain, then n/4, and so on.

The space complexity is constant because no additional data structures proportional to the input size are created.

Test Cases

sol = Solution()

# Provided example, target exists
assert sol.search([-1, 0, 3, 5, 9, 12], 9) == 4

# Provided example, target does not exist
assert sol.search([-1, 0, 3, 5, 9, 12], 2) == -1

# Single element array, target exists
assert sol.search([5], 5) == 0

# Single element array, target does not exist
assert sol.search([5], 3) == -1

# Target at beginning of array
assert sol.search([1, 2, 3, 4, 5], 1) == 0

# Target at end of array
assert sol.search([1, 2, 3, 4, 5], 5) == 4

# Target in middle
assert sol.search([1, 2, 3, 4, 5], 3) == 2

# Target smaller than all elements
assert sol.search([10, 20, 30]()

LeetCode 704 - Binary Search