Find Greater or Equal

[Massimiliano Alberti]

Can someone check this? If it's OK, you can use however you want... :-)
It should search for an element in an array and, if it can't find it, return
the next element.
key is what you are searching, in a *base array of LONG with num elements.
After some tests it seems to work well (the original version was filled with
ASSERTs)
(I will use this function in a bigger look-for-or-insert function)

Some notes:
The function returns the index of the element.
2, 2, 2, 3. Search for 2, it will return the second one (index = 1)
1, 2, 2, 4. Search for 2, it will return the first one (index = 1)
But it should always return the first bigger-than-key element, if it can't
find key (this is very important. I have to insert a new element in that
place, and I want the array to be still ordered after the insertion)
If key > max(all-the-elements) then the function returns -1;

int FindGreaterOrEqual(LONG key, LONG *base, size_t num)
{
LONG lo = 0;
LONG hi = num - 1;
LONG mid;

size_t half;

if (!num || key > base[hi]) {
return -1;
}

while (lo != hi) {
if (num == 2) {
if (key < base[lo]) {
return lo;
}

return hi;
}

half = num / 2;

mid = lo + ((num & 1) ? half : (half - 1));

if (key == base[mid]) {
return mid;
} else if (key < base[mid]) {
hi = mid;
num = ((num & 1) ? (half + 1) : half);
} else {
lo = mid + 1;
num = half + 1;
}
}

return lo;
}

[Darrell Grainger]

On Fri, 20 Feb 2004, Massimiliano Alberti wrote:

Can someone check this? If it's OK, you can use however you want... :-)
It should search for an element in an array and, if it can't find it, return
the next element.
key is what you are searching, in a *base array of LONG with num elements.
After some tests it seems to work well (the original version was filled with
ASSERTs)
(I will use this function in a bigger look-for-or-insert function)
It is good that you are validating this function before attempting to use
it in another function. Working on parts at a time is always better than
trying to write a program as one big thing. However, validating a function
by testing it is not that great. Empirical testing will catch some bugs
but you really want to test your design/logic.
Some notes:
The function returns the index of the element.
2, 2, 2, 3. Search for 2, it will return the second one (index = 1)
1, 2, 2, 4. Search for 2, it will return the first one (index = 1)
But it should always return the first bigger-than-key element, if it can't
find key (this is very important. I have to insert a new element in that
place, and I want the array to be still ordered after the insertion)
If key > max(all-the-elements) then the function returns -1;
I'm assuming the list of numbers is sorted in non-descending order.
int FindGreaterOrEqual(LONG key, LONG *base, size_t num)
{
LONG lo = 0;
LONG hi = num - 1;
LONG mid;
size_t half;
Why is half a size_t data type and the others are LONG?
if (!num || key > base[hi]) {
return -1;
}
First case: Key is greater than all elements in the array. Pretty straight
forward.
while (lo != hi) {
if (num == 2) {
if (key < base[lo]) {
return lo;
}
return hi;
}
Second case: There are only 2 elements in the array. There is a mistake
here. Try:

LONG base[] = {2, 4};
LONG key = 2;
half = num / 2;
mid = lo + ((num & 1) ? half : (half - 1));
You might want to put some comments if this is homework. It is pretty
obvious to me what (num & 1) is meant to do here. It is also not
immediately obvious that num==1 will work for this function. Are you
sure the function works if num==1? There are 3 cases to test if num==1.
if (key == base[mid]) {
return mid;
} else if (key < base[mid]) {
hi = mid;
num = ((num & 1) ? (half + 1) : half);
} else {
lo = mid + 1;
num = half + 1;
}
}

return lo;
}

At this point I look at this code and think you could write it a little
more clear. I see at least one bug in it.

--
Send e-mail to: darrell at cs dot toronto dot edu
Don't send e-mail to vi************@whitehouse.gov

[Massimiliano Alberti]

Second try... Fully commented. I have corrected two errors, the key <=
base[lo] and the num = half + 1 that now is a num = half.
I'm using size_t for num and half while using LONG for the index because
this is not the original program... You don't want to see something very
very ugly very very based on pointers :-) It's much more readable if you see
indexes and LONGs. To obtain the real program you have to imagine that LONG
is void* (casted to char* to be used), base[something] is something without
base (where something is a char*), that even key is a char* and that the
simple <, >, = are functions that compare (yes, it's lousily based on the
bsearch function). Quite ugly! :-)
The program is based on the method of bisection. We take the middle element
and then decide which half of the array is the "good" half. We repeat the
process. Sometimes we have to include the middle element in the "good" half,
sometimes not. In the end we will have an array of one or two elements. If
we have only one element the while will die and we will return the index of
the element. If we have two elements then we analyze the first one and then
we decide.

int FindGreaterOrEqual(LONG key, LONG *base, size_t num)
{
LONG lo = 0; // Index of first element. Note that lo and hi will be
changed as we bisect the array. So will num (the number of elements between
lo and hi), half (half of num) and mid (index of the middle element)
LONG hi = num - 1; // Index of last element
LONG mid; // Index of middle element

size_t half; // half-number of elements (number of lo-mid elements)

if (!num || key > base[hi]) { // if no elements or key > highest element
(last element), return -1
return -1;
}

while (lo != hi) { // if there is a single element then we don't have to
analyze
assert(num == (hi - lo + 1)); // just to be sure
if (num == 2) { // if we have only two elements, then the bisection
method doesn't work
if (key <= base[lo]) { // compare with first element, if key <=
base[lo], then return lo
return lo;
}

return hi; // return hi
}

half = num / 2; // half number of elements

mid = lo + ((num & 1) ? half : (half - 1)); // if num is odd (num &
1), then we will use (half + 1) elements (so we will round half to the next
integer), if even half elements

if (key == base[mid]) { // if the middle element is == key, then
return it's index.
return mid;
} else if (key < base[mid]) { // if the key is lesser than the middle
element, then we bisect on the middle element. We have to include the middle
element because it could be the first element greater-than.
hi = mid;
num = ((num & 1) ? (half + 1) : half); // we recalc the number of
elements of the sub-lists. The first sublist is the
half/half.5-rounded-to-half+1 list
} else {
lo = mid + 1; // the key is greater than the middle element. We
bisect on the middle element. We can exclude the middle element because it
can't be the first greater-than element and we have already compared it with
key
num = half; // we recalc the number of elements of the sub-lists.
The second sublist always has half elements (the odd element is always
included in the first one)
}
}

return lo; // single element case: return the index of the element.
}

[David Rubin]

Massimiliano Alberti wrote:

[snip - explanation of binary search]
[comments and asserts removed for readability]

int FindGreaterOrEqual(LONG key, LONG *base, size_t num)
{
LONG lo = 0;
LONG hi = num - 1;
LONG mid;

size_t half; // half-number of elements (number of lo-mid elements)

if (!num || key > base[hi]) {
return -1;
}
This is an optimization. IMO, you don't need this as num==0 is a programmer
error, and key > base[hi] will be caught by the more general expression below.
while (lo != hi) {
if (num == 2) {
if (key <= base[lo]) {
return lo;
}
return hi;
}
half = num / 2;
You don't need to check if num==2, and you don't need to compute half.
mid = lo + ((num & 1) ? half : (half - 1));
This is a terrible expression. Generally speaking, you should not mix arithmetic
and bit-wise operations. In any case, it doesn't matter where your midpoint is
because key will always be in the range (lo,mid) or (mid+1,hi).

if (key == base[mid]) {
return mid;
} else if (key < base[mid]) {
hi = mid;
This should be mid+1. Since you know key is not at mid, there is no reason to
keep mid in the new range.
num = ((num & 1) ? (half + 1) : half);
The algorithm is much simpler if you hold on to num!
} else {
lo = mid + 1;
num = half;
Ditto.
}
}
return lo;
You should always return mid here since the element is either at mid, or
mid==low==0. This is consistent with checking whether key == base[mid].
}

Here is how you might write this without changing num:

int
bsearch_ge(long key, long *base, int num)
{
int l = 0;
int h = num-1;
int m = (l+h)/2;

/* generic binary search */
while(l < h){
if(key == base[m])
return m;
if(key < base[m])
h = m - 1;
else
l = m + 1;
m = (l+h)/2;
}

/* l==h; apply "greater than or equal to" logic */
if(key > base[m]){
if(m < num-1)
return m+1; /* key > base[m] && m < num-1 */
else
return -1; /* key > base[m] && m == num-1 */
}
return m; /* key <= base[m] */
}

/david

--
Andre, a simple peasant, had only one thing on his mind as he crept
along the East wall: 'Andre, creep... Andre, creep... Andre, creep.'
-- unknown