Click here to Skip to main content
15,029,039 members
Please Sign up or sign in to vote.
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

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




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