Debug binary search code

Question

I came across this interview questions. It says we have to do a binary search on a sorted array. Following is the code for that. This code has bug such that it doesn't give right answer. You have to change the code to give correct output.

Condition : You are not allowed to add line and you can change only three lines in the code.

int solution(int[] A, int X) {
    int N = A.length;
    if (N == 0) {
        return -1;
    }
    int l = 0;
    int r = N;
    while (l < r) {
        int m = (l + r) / 2;
        if (A[m] > X) {
            r = m - 1;
        } else {
            l = m+1;
        }
    }
    if (A[r] == X) {
        return r;
    }
    return -1;
}

I tried a lot on my own but was missing on some test cases.

If number is the fisr number in the array that I am looking for. — Vallabh Patade
– Vallabh Patade, Commented Sep 25, 2014 at 19:46
In the loop, if the number is found (i.e. A[m] == X), l gets modified instead of returning it. — imreal
– imreal, Commented Sep 25, 2014 at 19:49
So imagine an array of 4 values (you provide them), and manually simulate the code on paper. As you get more experienced, you should be able to do this simulation in your head. — Ira Baxter
– Ira Baxter, Commented Sep 25, 2014 at 19:49

MattPutnam · Accepted Answer · 2014-09-25 20:02:56Z

0

I hate this question, it's one of those "unnecessary constraint" questions. As others have mentioned, the problem is that you're not returning the value if you find it. Since the stupid instructions say you can't add any code, you can hack it like this:

if (A[m] >= X) {
    r = m;
} else {
    l = m;
}

This kills the performance but it should work.

answered Sep 25, 2014 at 20:02

MattPutnam

3,0273 gold badges19 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Florian F Over a year ago

It will loop forever if the array has 1 element and it is <X : l=0, r=1, m=0, A[0]<X so l=0, and it loops forever.

NetVipeC · Accepted Answer · 2014-09-25 20:04:16Z

0

You need to check for the searched value inside the loop, for exit if it's found

Sample Code:

int solution(int[] A, int X) {
    int N = A.length;
    if (N == 0) {
        return -1;
    }
    int l = 0;
    int r = N;
    while (l <= r) { // change here, need to check for the element if l == r
                     // this is the principal problem of your code
        int m = (l + r) / 2;
        if (A[m] == X) { // new code, for every loop check if the middle element
            return r;    // is the search element for early exit.
        } else if (A[m] > X) {
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return -1;
}

Other problem is that you are testing more elements that you need when the element is in the array.

edited Sep 25, 2014 at 20:04

answered Sep 25, 2014 at 19:57

NetVipeC

4,4321 gold badge20 silver badges20 bronze badges

Comments

AstroCB · Accepted Answer · 2014-09-25 20:17:31Z

0

Try this:

int l = 0;
int r = N - 1; // changed
while (l <= r) { // changed

edited Sep 25, 2014 at 20:17

AstroCB

12.4k20 gold badges59 silver badges76 bronze badges

answered Sep 25, 2014 at 19:50

500 - Internal Server Error

29k8 gold badges64 silver badges78 bronze badges

1 Comment

Florian F Over a year ago

I think if the first element is >X, it will try to access A[-1].

Florian F · Accepted Answer · 2014-09-25 20:32:46Z

You have to understand the method that is used. You are looking for the first element >= X.

You want k with i < k <=> A[i] < X.

L is for left. It is the lower limit for k. You have i < l => A[i] < X.

R is for right. It is the upper limit for k. You have i >= r => A[i] >= X.

Your target is to reduce the range and have l = r. To do so you check the value in the middle, at m = (r+l)/2.
If A[m] >= X then m satisfies the conditions for r. You can set r = m.
If A[m] < X then A[m] belongs to the part left of l. So you can set l to the right of m, l = m+1.

Each loop reduces the range between l and r. When you reach l==r, you have found the point I called k. A[k] is the smallest number >= X. You only need to check if it is == X or > X.

From there you should be able to fix the code.

PS: Note that the k (aka l or r) can be >= A.length. You need to verify that.

Collectives™ on Stack Overflow

Debug binary search code

4 Answers 4

1 Comment

Comments

1 Comment

Comments

Your Answer

Collectives™ on Stack Overflow

Debug binary search code

4 Answers 4

1 Comment

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related