Customizing compare in bsearch()

Question

I have an array of addresses that point to integers ( these integers are sorted in ascending order). They have duplicate values. Ex: 1, 2, 2, 3, 3, 3, 3, 4, 4......

I am trying to get hold of all the values that are greater than a certain value(key). Currently trying to implement it using binary search algo -

void *bsearch(
 const void *key,
 const void *base,
 size_t num,
 size_t width,
 int ( __cdecl *compare ) ( const void *, const void *)
);

I am not able to achieve this completely, but for some of them.

Would there be any other way to get hold of all the values of the array, with out changing the algorithm I am using?

Answer 1

You should look into std::upper_bound

For example, to find the address of the first value > 3:

const int data[] = { 1, 2, 2, 3, 3, 3, 3, 4, 4, ... };
size_t data_count = sizeof(data) / sizeof(*data);

const int *ptr = std::upper_bound(data, data + data_count, 3);

// ptr will now point to the address of the first 4

A related function is std::lower_bound.

Answer 2

Yes, you can use a binary search. The trick is what you do when you find an element with the given key... unless your lower and upper indices are the same, you need to continue binary searching in the left part of your interval... that is, you should move the upper bound to be the current midpoint. That way, when your binary search terminates, you will have found the first such element. Then just iterate over the rest.

Answer 3

As Klatchko and GMan have noted, the STL function gives you exactly what you're asking: std::upper_bound.

If you need to stick with bsearch, though, the simplest solution may be to iterate forwards until you reach a new value.

void* p = bsearch(key, base, num, width, compare);
while ((p != end) &&           // however you define the end of the array - 
                               // base + num, perhaps?
       (compare(key, p)==0)){  // while p points to an element matching the key

   ++p; // advance p
}

If you want to get the first p that matches key, rather than the first one that's larger, just use --p instead of ++p.

Whether you prefer this or a repeated binary search, as Michael suggests, depends on the size of the array and how many repetitions you expect.

Now, your question title refers to customizing the compare function, but as I understand the question that won't help you here - the compare function must compare any two equivalent objects as being equivalent, so it's no good for recognizing which of several equivalent objects is the first/last of its type in an array. Unless you had a different problem, specifically concerning the compare function?

Answer 4

If you have a binary search tree implemented, you have tree traversal algorithms to do this. You could reach the required 'upper-bound' node and simply traverse in-order from there. Traversal is simpler than searching the tree multiple times, i.e, traversing a tree of n nodes would take n operations at most, whereas searching n times would take (n.log n) operations.