Binary Search

Problem

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search for target in nums. If target exists, 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,8,12], target = 8
Output: 4

Explanation: 8 exists in nums and its index is 4.

Example 2

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

Explanation: 1 does not exist in nums, so return -1.

Solution

Binary search finds a target in an ascending sorted array by repeatedly discarding half of the remaining search range. The sorted order is essential: without it, comparing the middle value cannot tell us which half is safe to discard.

For example:

values: [3, 7, 12, 18, 25]
target: 18

range [0, 4] -> middle 2 -> 12 is too small, so move left to 3
range [3, 4] -> middle 3 -> 18 is the target

The algorithm keeps an inclusive range from left to right:

1. Start with left at the first index and right at the last.
2. While left <= right, inspect the middle value.
3. Return the middle index when it equals the target.
4. If it is smaller than the target, set left = middle + 1; otherwise, set right = middle - 1. The middle value has already been ruled out, so exclude it from the next range.
5. Return -1 when the range becomes empty.

Calculate the middle index as left + (right - left) / 2, using integer division. This avoids overflowing left + right in languages with fixed-size integers, such as C# and Go. Python uses // for integer division.

public static class Solution
{
    public static int BinarySearch(int[] nums, int target)
    {
        int left = 0;
        int right = nums.Length - 1;

        while (left <= right)
        {
            int middle = left + (right - left) / 2;

            if (nums[middle] == target)
                return middle;

            if (nums[middle] < target)
                left = middle + 1;
            else
                right = middle - 1;
        }

        return -1;
    }
}

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

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

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

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

	return -1
}

def binary_search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        middle = left + (right - left) // 2

        if nums[middle] == target:
            return middle

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

    return -1

Each version returns the index of a matching value or -1 when no match exists. An empty array therefore returns -1 without entering the loop.

Why it works

Throughout the loop, if the target exists, it must remain inside [left, right]. Because the array is sorted, a middle value smaller than the target also rules out every value to its left. A larger middle value rules out every value to its right.

Complexity

• Time: O(log n) because every comparison removes approximately half of the remaining range.
• Extra space: O(1) because the iterative version stores only a few indexes.

With duplicate values, this basic version may return any matching index. Variations of the same pattern can find the first match, last match, or insertion position. If the input is not already sorted, sorting it first costs O(n log n), so a linear scan may be better for a single search.