0
$\begingroup$

Give an array of integer has been sorted (non-decreasing order), we need find the index of minimum number number that is greater than key given, I wrote two functions, they're identical except the return lines.

int minimum_index_greater(int *a, int lo, int hi, int key) {
    int left = lo - 1;
    int right = hi + 1;

    while (left + 1 < right) {
        int mid = (left + right) / 2;

        if (a[mid] > key) right = mid;
        else              left = mid;
    }

    return right;    -------> function 1
    return left + 1; -------> function 2
}

The first question is any of them is correct (return the right value) ?

The second question is, I suppose two functions are the same in this situation, they return the same value in every case. And I pretty sure about that. Am i right or not ? please explain.

P/S : When I solve a problem on Sphere Online Judge. I need to find this value and solve the problem, use function 1, I got 97.72/100 point (which I have no idea why isn't it 100), use function 2, I only got 94.44. So I guess the problem is here

|cite|improve this question
$\endgroup$
  • $\begingroup$ May be your score is low because you do not treat the condition when the key is not found. And are a[lo] and a[hi] the first and the last elements of the array respectively? $\endgroup$ – PleaseHelp Aug 17 '15 at 16:08
  • 1
    $\begingroup$ Welcome to CS.SE! What have you tried? Have you tried running it on many test cases? Were they correct on all test cases you tried? Have you tried proving it correct? Have you tried find a suitable loop invariant for the loop and proving whether you always have right == left+1 after the loop? We expect you to make a serious effort to solve it on your own before asking, and to show us what you tried. Please edit the question to show us what you've tried and where you got stuck -- it helps us give you better answers and makes the question more useful to others. $\endgroup$ – D.W.♦ Aug 17 '15 at 17:27
  • 1
    $\begingroup$ Could you describe what are this magic constants (lo - 1), (hi + 1)? It looks like binary search with some additional work. If you declare something as $left = lo - 1;$ then use it as $left + 1$ then overwrite and still add it becomes confusing. $\endgroup$ – Evil Aug 17 '15 at 17:54
  • $\begingroup$ @IvayloStrandjev The initialization 'left = lo - 1' and 'right = hi + 1' is totally intent, because I want the left and right position are already checked in every iteration, that also why I set 'left = mid' or 'right = mid' at the end of iteration, because they were checked $\endgroup$ – dandoh Aug 17 '15 at 20:53
  • $\begingroup$ "Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky" — Donald Knuth $\endgroup$ – Hendrik Jan Aug 18 '15 at 2:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.