I cannot understand why my function exceeds time limit and why it can go into an infinite loop. Is there an edge case I might be overlooking?
Here is the problem description:
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.
var searchInsert = function(nums, target) {
if (target > nums[nums.length - 1]) { // If target is greater
return nums.length; // than the largest element
};
let leftIndex = 0; // implementing binary search
let rightIndex = nums.length - 1;
while (leftIndex != rightIndex) {
let pivot = Math.round((rightIndex + leftIndex) / 2);
if (target == nums[pivot]) {
return pivot;
} else if (target < nums[pivot]){
rightIndex = pivot - 1;
} else {
leftIndex = pivot + 1;
}
};
return target <= nums[leftIndex] ? leftIndex : leftIndex + 1;
};const array = [1, 2, 6, 8, 10, 16, 18, 20, 33, 55]
function findTarget(target){
if(array.includes(target)){
return "Target was found at index : " + array.indexOf(target)
}
if(array[0] > target)
return "Target should be inserted at index : " + 0
for(let i = 0; i < array.length; i+=1){
if(array[i] < target && array[i + 1] > target){
return "Target should be inserted at index : " + (i+1)
}
}
return "Target should be inserted at index : " + array.length
}
console.log(findTarget(8))
console.log(findTarget(9))
console.log(findTarget(60))
console.log(findTarget(0))You could use a condition which really stops the loop, for example by checking left and right and if left is greater than right exit the loop.
while (leftIndex < rightIndex) {
Another part is to floor the pivot index, either by using Math.floor or by >> right shift.
const pivot = (rightIndex + leftIndex) >> 1; // right shift by one bit
This prevents to omit some indices and produces predictable results.
To check all use an array with even and odd items and check every value of the array.
var searchInsert = function(nums, target) {
let leftIndex = 0;
let rightIndex = nums.length - 1;
if (target > nums[rightIndex]) return nums.length;
while (leftIndex < rightIndex) {
const pivot = (rightIndex + leftIndex) >> 1;
if (target === nums[pivot]) return pivot;
if (target < nums[pivot]) rightIndex = pivot - 1;
else leftIndex = pivot + 1;
};
return target <= nums[leftIndex] ? leftIndex : leftIndex + 1;
};
console.log(searchInsert([0, 1, 2, 3, 4, 5], -0.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 0));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 0.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 1));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 1.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 2));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 2.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 3));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 3.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 4));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 4.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 5));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 5.5));
console.log('--');
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], -0.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 0));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 0.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 1));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 1.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 2));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 2.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 3));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 3.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 4));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 4.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 5.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 6));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 6.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 7));.as-console-wrapper { max-height: 100% !important; top: 0; }