easy

Binary Search

Find the index of a target value in a sorted array.

1. Define the problem

Binary Search

Given an array of integers nums sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity. Keep two bounds, low and high , and compare the target against the value at the midpoint each step, discarding the half that cannot hold it.

Constraints

  • 1 ≤ nums.length ≤ 104
  • -104 < numsi, target < 104
  • All the integers in nums are unique
  • nums is sorted in ascending order

Example

Inputnums = [-1, 0, 3, 5, 9, 12], target = 9
Output4

Explanation 9 exists in nums and its index is 4.

2. Know the words first

In plain terms

O(log n)
Grows so slowly that doubling the input only adds one more step — a million elements takes about twenty comparisons instead of a million.
3. Visualize the solution

Halve the search range until the target is found

Halve the search range until the target is found
Statusinit

low=0, high=5, mid=2 (value 3). 9 > 3, so low moves to 3.

What happens in this step

low=0, high=5
mid = 0 + floor((5-0)/2) = 2, nums[2] = 3

3 < 9, so the target must be to the right of mid — mid and everything left of it is discarded. low becomes 3.
Step 1 of 3

Steps to visualize

  1. The row is the whole array; the box marks the part still being searched.
  2. Start low at index 0 and high at the last index.
  3. Compare numsmid to the target.
  4. If they match, return mid.
  5. If numsmid is smaller, move low to mid + 1.
  6. If numsmid is larger, move high to mid - 1.
  7. If low passes high, the target is not present — return -1.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Halve the search range until the target is found
Statusinit

low=0, high=5, mid=2 (value 3). 9 > 3, so low moves to 3.

What happens in this step

low=0, high=5
mid = 0 + floor((5-0)/2) = 2, nums[2] = 3

3 < 9, so the target must be to the right of mid — mid and everything left of it is discarded. low becomes 3.
Step 1 of 3
5. Solution

Solution

solution.tsTypeScript
function search(nums, target) {
  let low = 0;
  let high = nums.length - 1;

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);

    if (nums[mid] === target) {
      return mid;
    }
    if (nums[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
}
Time
O(log n)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
nums = [-1, 0, 3, 5, 9, 12], target = 94example from the docstring
nums = [-1, 0, 3, 5, 9, 12], target = 2-1target absent from the array
nums = [5], target = 50smallest valid input, target present
nums = [5], target = -5-1smallest valid input, target absent
nums = [-1, 0, 3, 5, 9, 12], target = -10target is the first element
nums = [-1, 0, 3, 5, 9, 12], target = 125target is the last element
nums = [2, 5, 8, 12], target = 82even-length array with no exact middle

Keep reading