Binary Search LeetCode Solution (Easy) (2026)

Approach Summary

Classic binary search. Use mid = left + floor((right - left) / 2) to avoid overflow. While left <= right.

Practice Mode

Solve it yourself before revealing the code

DSA interviews test reasoning from brute force to optimal. Think through the constraints first.

Full Solution & Approach

Binary search repeatedly halves the search space. Maintain two bounds lo and hi that bracket the target, with the invariant that if the target exists it lies in [lo, hi]. At each step compute mid = (lo + hi) // 2. If nums[mid] equals target, return mid. If nums[mid] is less than the target, the target must be to the right, so set lo = mid + 1 (mid is already checked). Otherwise set hi = mid - 1. The loop ends when lo > hi, meaning the range is empty and the target is absent — return -1. Each comparison removes roughly half the remaining candidates, so after k steps the search space shrinks from n to about n / 2^k. This only works because the array is sorted — that precondition is what makes the halving valid.

Each iteration halves the range, so the number of iterations is log₂(n) — O(log n) time. Only constant extra space for three integers — O(1).

Solution Code

Solution

public 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;
        else if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int search(const 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;
        else if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

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
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

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

Edge Cases to Watch

Target smaller than every element — lo keeps moving right, ends with -1
Target at index 0
Target at the last index
Empty array or single-element array
Duplicate values — any matching index is acceptable

Algorithmic Pattern

Master the Binary Search Pattern

View Pattern Guide →

Study the core invariant, step-by-step decision framework, and common interview traps for the Binary Search pattern.

Framework: Binary Search • Interview Prep: Tested at FAANG • Explore all Binary Search problems & invariants →

How to Recognize This Pattern

Sorted array
Find exact target

Complexity Analysis

Time Complexity

O(log n)

Space Complexity

O(1)

Frequently Asked Questions

What is the optimal time and space complexity for Binary Search?

The optimal solution for Binary Search achieves O(log n) runtime complexity and requires O(1) auxiliary space. Each iteration halves the range, so the number of iterations is log₂(n) — O(log n) time. Only constant extra space for three integers — O(1).

How do I identify that Binary Search requires the Binary Search pattern?

In technical interviews, look for key problem signals: Sorted array; Find exact target. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Binary Search strategy.

What critical edge cases must be handled in Binary Search?

Essential edge cases to verify include: Target smaller than every element — lo keeps moving right, ends with -1; Target at index 0; Target at the last index; Empty array or single-element array. Always walk through these scenarios with your interviewer before coding.

Which tech companies frequently ask Binary Search?

Binary Search is a Easy-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Google, Facebook.

Binary Search LeetCode Solution