Problem statement

Given a sorted (ascending) array nums of distinct integers and a target, return the index of target if it exists, otherwise -1.

Your algorithm must run in O(log n) time.

Example 1

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

Example 2

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

Constraints

• 1 <= nums.length <= 30
• -100 <= nums[i], target <= 100
• All values are distinct; nums is sorted ascending.

Hints for Binary Search

1. Hint 1

   Compare the middle element with the target and discard half the array.

2. Hint 2

   Careful with the loop condition: lo <= hi, and move past mid on each side.

How to solve Binary Search

Sorted order means one comparison tells you which half of the array the target cannot be in. Look at the middle element and throw away half the search space each step, so the range collapses in log n comparisons instead of n.

Approach

1. Keep an inclusive range [lo, hi], initially the whole array.
2. Take mid = lo + (hi - lo) / 2.
3. If nums[mid] is the target, return mid.
4. If it is smaller, everything at or left of mid is too small — set lo = mid + 1.
5. Otherwise set hi = mid - 1. When lo > hi the range is empty and the target is absent.

Why it works

The invariant is that if the target exists it lies within [lo, hi]. Each comparison rules out mid and one whole side without examining them, because sortedness guarantees everything on the discarded side compares the same way. The range shrinks by at least one element per iteration and always excludes mid, so the loop terminates — and it halves, giving the logarithmic bound.

Complexity

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

Pitfalls

• With an inclusive hi, the loop condition must be lo <= hi. Using < skips the final single-element range.
• Move past mid (mid + 1 / mid - 1). Assigning lo = mid or hi = mid here loops forever.
• Compute the midpoint as lo + (hi - lo) / 2 rather than (lo + hi) / 2 — the latter can overflow on large bounds, a habit worth keeping even when the constraints are small.

Reference solution

Python

from typing import List

def search(nums: List[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Java

public static int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

C++

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

JavaScript

var search = function(nums, target) {
    let lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        if (nums[mid] === target) return mid;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy