Binary Search

Problem

Given a sorted array of integers and a target value, return the index of the target or -1 if it does not exist.

Approach

Classic two-pointer binary search. Set left = 0 and right = n - 1. On each iteration compute mid and compare nums[mid] to the target. Halve the search space by moving the appropriate pointer.

Solution

1function search(nums: number[], target: number): number {
2  let left = 0;
3  let right = nums.length - 1;
4 
5  while (left <= right) {
6    const mid = Math.floor((left + right) / 2);
7 
8    if (nums[mid] === target) return mid;
9    if (nums[mid] < target) left = mid + 1;
10    else right = mid - 1;
11  }
12 
13  return -1;
14}

Complexity