Coding problem · Easy · Binary Search

Binary Search

Easy Algorithms & data structures Seen at Microsoft, Apple, Adobe

Given a sorted (ascending) array of distinct integers nums and an integer target, return the index of target, or -1 if it is not present. Your algorithm must run in O(log n).

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 <= 10^4

Hints

Hint 1

Keep lo and hi as the inclusive bounds where the target could be; compare with the middle and discard half.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(log n) · Space O(1)

Maintain the invariant that the target, if present, is within [lo, hi]. Compute mid = lo + (hi - lo) / 2 (avoids overflow in fixed-width integers) and move one bound past mid each step.

Reference solution

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

function search(nums: number[], target: number): number {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] === target) return mid;
    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
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

<?php

function search(array $nums, int $target): int
{
    [$lo, $hi] = [0, count($nums) - 1];
    while ($lo <= $hi) {
        $mid = intdiv($lo + $hi, 2);
        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;
    }
}

Common mistakes

while (lo < hi) with hi = mid - 1 misses single-element ranges — be consistent about inclusive bounds.
(lo + hi) / 2 can overflow in Java/C++.

Search in Rotated Sorted Array · Medium