The solution is in the name of the problem: binary search.

Recursive approach

var searchResursive = function (nums, target, left, right) {
  if (left > right) {
    return -1;
  }

  let mid = (left + (right - left) / 2) | 0; // Integer division in JS

  if (nums[mid] === target) {
    return mid;
  } else if (target < nums[mid]) {
    return searchResursive(nums, target, left, mid - 1);
  } else {
    return searchResursive(nums, target, mid + 1, right);
  }
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  return searchResursive(nums, target, 0, nums.length - 1);
};

Iterative approach

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let left = 0;
  let right = nums.length - 1;
  let mid = 0;

  while (left <= right) {
    mid = (left + (right - left) / 2) | 0; // Integer division in JS

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

  return -1;
};

Complexity

  • Time Complexity: O(logN), or how many times can we halve the array until a single element remains.
  • Space Complexity: O(1), we are not using any extra memory, just moving pointers.

All Solutions