Binary Search

EasyArray Binary Search

A warehouse robot keeps the numbers of the storage bins along one aisle in a list, nums, sorted in ascending order with no number repeated. Bins to the left of the entrance have negative numbers. When an order arrives for bin target, the robot needs that bin's position in the list.

Return the index of target in nums, or -1 if there is no such bin. The robot's controller is slow, so the lookup must take O(log n) time.

Example 1

Input: nums = [-20,-5,0,8,13,40,77], target = 13
Output: 4

Explanation: Bin 13 is at index 4.

Example 2

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

Explanation: 5 would sit between 4 and 6, but no bin has that number.

Example 3

Input: nums = [-7], target = -7
Output: 0

Constraints

nums holds between 1 and 10^4 bin numbers in ascending order.
No bin number appears twice.
Every bin number, and target, is strictly between -10^4 and 10^4.

💡 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