LeetCode #35 Search Insert Position with JavaScript

Solution to LeetCode's 35. Search Insert Position with JavaScript.

You must write an algorithm with O(log n) runtime complexity.

Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const searchInsert = (nums, target) => {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] == target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return left;
};

• Time complexity: O(log n)
• Space complexity: O(1)

Linear search would result in a time complexity of O(n), so I used a binary search to reduce it to O(log n).