Search Insert Position

Problem Statement

Constraints

Solution 1: Binary Search for Insert Position

function searchInsertBinarySearch(arr, target) {
    let st = 0;
    let end = arr.length - 1;
    let ans = arr.length; // Initialize ans to the end of the array

    while (st <= end) {
        const mid = Math.floor(st + (end - st) / 2);
        if (target === arr[mid]) {
            return mid;
        }
        if (target < arr[mid]) {
            end = mid - 1;
            ans = mid; // Update ans to the current mid
        } else {
            st = mid + 1;
        }
    }
    return ans;
} 

const nums1 = [1,3,5,6];
const target1 = 5;
searchInsertBinarySearch(nums1,target1);  //output: 2 

const nums2 = [1,3,5,6];
const target2 = 2;
searchInsertBinarySearch(nums2,target2);  //output: 1 

const nums3 = [1,3,5,6];
const target3 = 7;
searchInsertBinarySearch(nums3,target3);  //output: 4 

Solution 2: Linear Search for Insert Position

function searchInsert(nums, target) {
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === target) {
            return i;
        }
        if (target > nums[i]) {
            count++;
        }
    }
    return count;
} 

const nums1 = [1,3,5,6];
const target1 = 5;
searchInsert(nums1,target1);  //output: 2 

const nums2 = [1,3,5,6];
const target2 = 2;
searchInsert(nums2,target2);  //output: 1 

const nums3 = [1,3,5,6];
const target3 = 7;
searchInsert(nums3,target3);  //output: 4 

Solution 3: Binary Search with Lower Bound for Insert Position

function searchInsertLowerBound(nums, target) {
    let left = 0;
    let right = nums.length;

    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
} 

const nums1 = [1,3,5,6];
const target1 = 5;
searchInsertLowerBound(nums1,target1);  //output: 2 

const nums2 = [1,3,5,6];
const target2 = 2;
searchInsertLowerBound(nums2,target2);  //output: 1 

const nums3 = [1,3,5,6];
const target3 = 7;
searchInsertLowerBound(nums3,target3);  //output: 4 

Solution 4: Linear Search for Insert Position in Sorted Array

function searchInsertLS(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] >= target) {
            return i;
        }
    }
    return nums.length;
} 

const nums1 = [1,3,5,6];
const target1 = 5;
searchInsertLS(nums1,target1);  //output: 2 

const nums2 = [1,3,5,6];
const target2 = 2;
searchInsertLS(nums2,target2);  //output: 1 

const nums3 = [1,3,5,6];
const target3 = 7;
searchInsertLS(nums3,target3);  //output: 4 

Solution 5: Recursive Binary Search for Insert Position

function searchInsertRecursive(nums, target) {
    function binarySearch(nums, target, start, end) {
        if (start > end) {
            return start;
        }
        
        const mid = Math.floor(start + (end - start) / 2);
        
        if (nums[mid] === target) {
            return mid;
        }
        if (nums[mid] < target) {
            return binarySearch(nums, target, mid + 1, end);
        }
        return binarySearch(nums, target, start, mid - 1);
    }

    return binarySearch(nums, target, 0, nums.length - 1);
} 

const nums1 = [1,3,5,6];
const target1 = 5;
searchInsertRecursive(nums1,target1);  //output: 2 

const nums2 = [1,3,5,6];
const target2 = 2;
searchInsertRecursive(nums2,target2);  //output: 1 

const nums3 = [1,3,5,6];
const target3 = 7;
searchInsertRecursive(nums3,target3);  //output: 4 

Solution 6: Linear Scan

function searchInsertPositionMethod(nums, target) {
  const arrLength = nums.length;
  if (arrLength === 0) throw new Error("Empty Array");

  for (let i = 0; i < arrLength; i++) {
    if (nums[i] === target) return i; // Target found, return the index
    if (nums[i] > target) return i; // Target should be inserted before this index
  }

  // If target is greater than all elements, return the length of the array
  return arrLength;
} 

const nums1 = [1,3,5,6];
const target1 = 5;
searchInsertPositionMethod(nums1,target1);  //output: 2 

const nums2 = [1,3,5,6];
const target2 = 2;
searchInsertPositionMethod(nums2,target2);  //output: 1 

const nums3 = [1,3,5,6];
const target3 = 7;
searchInsertPositionMethod(nums3,target3);  //output: 4 

Solution 7: Search Insert Position using exponentaion search algorithm

function searchInsertExponentialSearch(arr, target) {
    const n = arr.length;

    // If the array is empty
    if (n === 0) {
        return 0;
    }

    // If the target is less than the first element
    if (target <= arr[0]) {
        return 0;
    }

    // Find the range where the target could be
    let index = 1;
    while (index < n && arr[index] < target) {
        index *= 2;
    }

    // Perform binary search within the range
    let left = Math.floor(index / 2);
    let right = Math.min(index, n - 1);

    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        if (arr[mid] === target) {
            return mid;
        }
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    // If target is not found, `left` will be the insertion point
    return left;
} 

const nums1 = [1,3,5,6];
const target1 = 5;
searchInsertExponentialSearch(nums1,target1);  //output: 2 

const nums2 = [1,3,5,6];
const target2 = 2;
searchInsertExponentialSearch(nums2,target2);  //output: 1 

const nums3 = [1,3,5,6];
const target3 = 7;
searchInsertExponentialSearch(nums3,target3);  //output: 4 

More Problems Solutions