Stuck in this question (arrays)

Question

1.00/5 (2 votes)

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 18-Jun-21 3:08am

_-_-_-me

Updated 12-Aug-23 22:16pm

Add a Solution

3 solutions

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.

Posted 18-Jun-21 4:35am

CPallini

Updated 18-Jun-21 4:36am

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;
}

Posted 18-Jun-21 11:45am

Patrice T

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?

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

OriginalGriff · Accepted Answer · 2021-06-18T03:17:00

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.

Posted 18-Jun-21 3:17am

OriginalGriff

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