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