Skip to content
Advertisement

Search Insert Position-Wrong answe

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.

JavaScript

below is my code.Please help me know where the bug is.Thanks in advance

JavaScript

submission details

JavaScript

Advertisement

Answer

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:

JavaScript

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:

JavaScript

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).

User contributions licensed under: CC BY-SA
2 People found this is helpful
Advertisement