b*****n
发帖数: 143 | 1 "Programming Pearls" has a binary search program that searches the first
occurrence of a certain value. I think it is a little confusing so I wrote
it in another way:
/* Function that returns the first occurrence of x.
* arr is input sorted array, arr_size is the number of elements in arr,
* x is the value that we are looking for.
* Returns index of the element, or -1 if element is not found. */
int first_occurrence(int* arr, int arr_size, int x)
{
int l = 0;
int u = arr_size - 1;
while (l + 1 < u) {
int m = l + (u - l) / 2;
if (arr[m] < x)
l = m + 1; // line 8: both "l = m" and "l = m + 1" will work here?
else
u = m;
}
if (arr[l] == x)
return l;
if (arr[u] == x)
return u;
return -1;
}
My question is on line 8 (see the comments on that line). I tested a few
cases and it seems that both "l = m" or "l = m + 1" will work. Can anybody
confirm that? Thanks. | r*******n
发帖数: 3020 | 2 I think it's right.
loop invariant: x[l]<=t<=x[u] and x[l] is left most one.
at end of loop, u = l+1, and you check x[l] and x[u].
I can't find anything you miss.
first
wrote
arr,
【在 b*****n 的大作中提到】
: "Programming Pearls" has a binary search program that searches the first
: occurrence of a certain value. I think it is a little confusing so I wrote
: it in another way:
: /* Function that returns the first occurrence of x.
: * arr is input sorted array, arr_size is the number of elements in arr,
: * x is the value that we are looking for.
: * Returns index of the element, or -1 if element is not found. */
: int first_occurrence(int* arr, int arr_size, int x)
: {
: int l = 0;
| b*****n
发帖数: 143 | 3 Thanks. Your confirmation makes me feel better. |
|
