I'm solving a problem (leetcode 35). My code was accepted in run code result but when I submit it returns wrong answer.I don't really understand what is wrong in my answer .
Given a sorted array 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.
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
Example 4:
Input: [1,3,5,6], 0
Output: 0
below is my code.Please help me know where the bug is.Thanks in advance
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
var min = 0;
var max = nums.length - 1;
var guess;
while(min <= max) {
guess = Math.floor((max + min) / 2);
if (nums[guess] === target) {
return guess;
}
else if (nums[guess] < target) {
min = guess + 1;
}
else {
max = guess - 1;
}
}
};
submission details
Input: [1,3,5,6]
2
Output: undefined
Expected: 1
It is because you are missing the case where the target number is not found. In those cases you need to return the index where the target number can be inserted in the input array while the array stays sorted.
Here's a correct version of you JS code:
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
var min = 0;
var max = nums.length - 1;
let guess = 0
while(min <= max) {
const mid = Math.floor((max + min) / 2);
if (nums[mid] === target) {
return mid;
}
else if (nums[mid] < target) {
min = mid + 1;
guess = mid+1
}
else {
max = mid - 1
guess = mid;
}
}
return guess
};
You initially set guess to 0. While you binary search, if you find target, just return mid which is the mid point between the current min and max.
But if nums[mid] is smaller than target you can be sure that target needs to be inserted at least at mid+1 because nums[mid] needs to be to the left of target for the array to stay sorted.
On the other hand, if nums[mid] > target, target must push nums[mid] and everything to its right to the right and occupy the index of the element at nums[mid]. So, in this case, we set guess = mid.
At the end we return guess. That's because we haven't the target in the array.
Here is an arguably more elegant but a little bit harder to read solution:
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
let left = 0;
let right = nums.length
while(left < right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] < target) {
left = mid + 1;
}
else {
right = mid
guess = mid;
}
}
return left
};
If you have understood the previous solution, go through this and try to understand how it works.
Also note that to avoid overflow you need to calculate mid with left + IntergerDivide(right - left).