435,346 Members | 2,158 Online
Need help? Post your question and get tips & solutions from a community of 435,346 IT Pros & Developers. It's quick & easy.

# Find Greater or Equal

 P: n/a 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; } Nov 14 '05 #1
3 Replies

 P: n/a 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 Nov 14 '05 #2

 P: n/a 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. } Nov 14 '05 #3

 P: n/a 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 Nov 14 '05 #4

### This discussion thread is closed

Replies have been disabled for this discussion.