You are given a sorted array of distinct integers and a target value. Your task is to find the index of the target value if it exists in the array. If the target is not found, you need to determine the index where it should be inserted to maintain the sorted order.
To solve this problem, you must write an efficient algorithm.
Input: nums = [1,3,5,6] , target = 5
Output: 2
Input: nums = [1,3,5,6] , target = 2
Output: 1
Input: nums = [1,3,5,6] , target = 7
Output: 4
The length of the array, nums, is between 1 and 10,000.
Each integer in nums is between -10,000 and 10,000.
The array nums contains distinct values sorted in ascending order.
The target value is between -10,000 and 10,000.
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
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
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
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
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
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
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