23. Binary Search

You are given an array nums of distinct integers sorted in ascending order, and an integer target.

Return the index of target in nums, or -1 if it does not appear. Your algorithm should run in O(log n) time.

Example 1

Input: nums = [-4,-1,2,7,10,15], target = 7
Output: 3

Explanation: nums[3] is 7.

Example 2

Input: nums = [1,3,5,8], target = 4
Output: -1

Explanation: 4 would sit between 3 and 5, but it is not in the array.

Example 3

Input: nums = [6], target = 6
Output: 0

Constraints

1 <= nums.length <= 10^4
-10^4 < nums[i], target < 10^4
All values in nums are distinct
nums is sorted in ascending order

💡 Hint 1

Look at the middle element. If it is too small, can the target be anywhere to its left?

💡 Hint 2

Keep a window [lo, hi] that must contain the target if it exists, and halve it on every step.

💡 Hint 3

Stop when the window becomes empty (lo > hi); that means the target is absent.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Maintain a closed window [lo, hi] that is guaranteed to contain target if it exists. Compare nums[mid] with the target: equal means you are done, smaller means the answer can only be to the right (lo = mid + 1), larger means it can only be to the left (hi = mid - 1). Each comparison throws away half the window, so at most about log₂ n steps run before the window is empty. Computing mid as lo + (hi - lo) / 2 avoids integer overflow in Java.

Time O(log n)Space O(1)

function search(nums, target) {
  let lo = 0;
  let 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;
}

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

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function search(nums, target) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit