Leetcode problem 44 - Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

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

Example 1:

Input: nums = [1,3,5,6], target = 5 Output: 2 Example 2:

Input: nums = [1,3,5,6], target = 2 Output: 1 Example 3:

Input: nums = [1,3,5,6], target = 7 Output: 4

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (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;
};

The function searchInsert takes a sorted array nums and a target value target as parameters and returns the index where the target value should be inserted or found.

Initialize left and right pointers at the beginning and end of the array, respectively.

Enter a while loop that continues as long as left is less than or equal to right.

Calculate the middle index mid using Math.floor((left + right) / 2).

Compare the value at the middle index nums[mid] with the target value:

If they are equal, it means the target is found, so return mid. If nums[mid] is less than the target, update left to mid + 1 to search in the right half of the current range. If nums[mid] is greater than the target, update right to mid - 1 to search in the left half of the current range. If the loop completes without finding the target, it means the target should be inserted into the array. Return the left pointer, which represents the insertion point.