21. Binary Search · DSA Practice

nums is sorted in ascending order with distinct values. Return the index of target, or -1 if it is not there. Your algorithm must run in O(log n).

Example 1

Input: nums = [-3,0,4,8,15], target = 8

Output: 3

Example 2

Input: nums = [-3,0,4,8,15], target = 5

Output: -1

Hint 1

Compare with the middle element and throw away the half that cannot contain the target.

Binary Search

Approach 1: Linear scan

Check every element.

⏱ Time O(n)💾 Space O(1)

Approach 2: Binary search ✅

Halve the search range each step.

⏱ Time O(log n)💾 Space O(1)

Reference solution for Binary search (time O(log n), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def search(self, 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        # target is in the right half
            else:
                hi = mid - 1        # target is in the left half
        return -1

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

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lo = 0, hi = (int)nums.size() - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;   // avoids int overflow
            if (nums[mid] == target) return mid;
            if (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 = (lo + hi) >> 1;
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1; else hi = mid - 1;
  }
  return -1;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Binary Search.