I wrote this code, but I dont uderstand why it works this way, especially using the third and fourth examples as input. Why the 'middle' position remains so behind? -in the number 5 (or index 2) using the [1, 3, 5, 6] array and the number 7 as target??
And how to make it better?? I cant think of a shorter or better way to check the if/elses when the target value is not in the array, especially if the input is an array with only one value and the target to find is 0. Maybe a better way to check the possible different scenarios. Or how to better check the correct place of the target without so many if/elses.
For example, is this code good enough to a coding interview? What can I do better?
from LeetCode:
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
And especially this one: Example 4: Input: nums=[1], target= 0
Constraints: 1 <= nums.length <= 104 -104 <= nums[i] <= 104 nums contains distinct values sorted in ascending order. -104 <= target <= 104
this is my code:
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
let left = 0;
let right = nums.length -1;
let middle;
while(left <= right){
middle = nums.length>1 ? (Math.floor(left + (right - left)/2)) : 0;
if(nums[middle] === target){
return middle;
} else if(target < nums[middle]){
right = middle -1;
} else {
left = middle + 1;
}
}
console.log(`Middle: ${middle}`);
console.log(`Middle-1: ${nums[middle-1]}`);
if(nums.lenght === 1){
return 0;
} else {
if((target < nums[middle] && target > nums[middle-1] )|| (target < nums[middle] && nums[middle-1] === undefined)){ /*
No more items to the left ! */
return middle;
} else if(target<nums[middle] && target<nums[middle-1]){
return middle-1;
} else if(target > nums[middle] && target > nums[middle + 1]) {
return middle + 2; /* Why the 'middle' is so behind here? using the THIRD example as input?? */
} else {
return middle + 1;
}
}
};
The issue lies in the variable you are checking for after the while loop.
In a "classical" binary search algorithm, reaching beyond the while loop would indicate the needle isn't present in the haystack. In case of this problem, though, we simply need to return right + 1 in this place in the code (rather than checking the middle).
Your code adjusted for this:
var searchInsert = function(nums, target) {
let left = 0;
let right = nums.length -1;
let middle;
while(left <= right){
middle = nums.length>1 ? (Math.floor(left + (right - left)/2)) : 0;
if(nums[middle] === target){
return middle;
} else if(target < nums[middle]){
right = middle -1;
} else {
left = middle + 1;
}
}
return right + 1;
};
console.log(
searchInsert([1,3,5,6], 5),
searchInsert([1,3,5,6], 2),
searchInsert([1,3,5,6], 7),
searchInsert([1], 0)
);Also, the below is redundant...
middle = nums.length>1 ? (Math.floor(left + (right - left)/2)) : 0;
...and can be shortened to:
middle = Math.floor((left + right) / 2);
const searchInsertProblem = (arr, n) => {
let start = 0;
let end = arr.length - 1;
while (start <= end) {
const middle = Math.floor((start + end) / 2);
if (arr[middle] === n) { return middle; } // on target
if (arr[middle] > n) { end = middle - 1; } // overshoot
else { start = middle + 1; } // undershoot
}
return end + 1;
};
console.log(
searchInsertProblem([1,3,5,6], 5),
searchInsertProblem([1,3,5,6], 2),
searchInsertProblem([1,3,5,6], 7),
searchInsertProblem([1], 0)
);