15,029,039 members
1.00/5 (1 vote)
See more:
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.

Answer:
When the target is found , we could return mid here.

But,

When the target is not present in the given sorted array ,
How can we predict in which index the target would be present if it were inserted in
in order?
I was not understanding whether to return l or h?

In that case we could experiment on a simple array and understand it. But we could not say in every case it turns out to be true.

Thank you!

What I have tried:

C++
```int searchInsert(int* nums, int numsSize, int target){
int l=0;
int h=numsSize-1;
int mid=(l+h)/2;
while(l<h)
{
if(target==nums[mid])
{
return nums[i];
}
else
if(target<nums[mid])
{
h=mid-1;
mid=(l+h)/2;
}
else
{
l=mid+1;
mid=(l+h)/2;
}
}
}```
Posted
Updated 18-Jun-21 11:45am

## Solution 1

If the element exists, return the index.

If it isn't, then remember the array is sorted: so if you added the value 4 to an array containing 1, 3, and 5 you would get 1, 3, 4, 5.
The index of the number you inserted would be 2 - so you return that.
Basically, return the index of the first number that is greater than or equal to the number you are looking for, or the length if you run out of elements to compare.
Comments
CPallini 18-Jun-21 9:29am

5.
OriginalGriff 18-Jun-21 9:57am

You wait - the next query will be "how do I do a O(log n) algorithm for that?"

If he's reading, then hint: it's a sorted array. Do you need to look at every element?
CPallini 18-Jun-21 10:12am

He is already doing that in O(log2(N)).
(if it works...)

## Solution 2

I think your binary search implementation is flawed (I hope I am right, this time...): the problematic statements being
C
`h=mid-1;`
and
C
`l=mid+1;`

`(nums[h] >= target)` and `(nums[l] <= target)` must hold, in order to make the binary search work.
v2
Comments
_-_-_-me 18-Jun-21 10:51am

Oh, Thank you :)

I should write l<=h in while loop ,right?
CPallini 18-Jun-21 10:58am

That would make the loop never ending.

## Solution 3

If you wonder why your code do not compile and you get a message like "All path must return a value".
It is because your code is missing a 'return'.
C++
```int searchInsert(int* nums, int numsSize, int target){
int l=0;
int h=numsSize-1;
int mid=(l+h)/2;
while(l<h)
{
if(target==nums[mid])
{
return nums[i];
}
else
if(target<nums[mid])
{
h=mid-1;
mid=(l+h)/2;
}
else
{
l=mid+1;
mid=(l+h)/2;
}
}
// a return is missing here
return h;
}```
Comments
_-_-_-me 18-Jun-21 21:46pm

Thank you !
But why we should only return h, why we should not return l ?
Patrice T 18-Jun-21 21:55pm

You choose the variable holding the correct answer.
_-_-_-me 18-Jun-21 22:03pm

How could we know which is correct variable?
If I take an example , in that case if l would be true
But in every case ,
How could we know which one would be true?

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Top Experts
Last 24hrsThis month
 Richard Deeming 150 Richard MacCutchan 100 CHill60 100 Patrice T 90 CPallini 80
 OriginalGriff 2,094 Richard Deeming 1,438 Richard MacCutchan 1,097 CPallini 840 Patrice T 550

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900