How to Get a "Useful" C++ Binary Search Algorithm

Where can I get a useful C++ binary search algorithm?

There is no such functions, but you can write a simple one using std::lower_bound, std::upper_bound or std::equal_range.

A simple implementation could be

template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
    // Finds the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end && !(val < *i))
        return i; // found
    else
        return end; // not found
}

Another solution would be to use a std::set, which guarantees the ordering of the elements and provides a method iterator find(T key) that returns an iterator to the given item. However, your requirements might not be compatible with the use of a set (for example if you need to store the same element multiple times).

More efficient way to do binary search in c++?

I am a proponent of binary search without comparison for equality, so that every reduction step takes a single comparison (you perform a single comparison for equality in the end, when the interval has shrunk).

The idea of comparison for equality is that you can terminate the search earlier when the key is found. If the key is found at depth d, this takes 2d comparisons. The average number of comparisons is twice the average depth of the tree, and is 2 Log2(N) - 1 for a perfect tree (early termination only spares one comparison).

This is to be compared to Log2(N) without equality test. Not counting that when the key is not found, the full depth of the tree is always traversed ! Testing for equality seems a false good idea.

Is there a Binary Search method in the C standard library?

There is the bsearch() method in the same <stdlib.h>, as is listed here, here and here.

The bsearch() function uses the binary search algorithm to find an element that matches key in a sorted array of n elements of size size. (The type size_t is defined in <stdlib.h> as unsigned int.) The last argument, compare, gives bsearch() a pointer to a function that it calls to compare the search key with any array element. This function must return a value that indicates whether its first argument, the search key, is less than, equal to, or greater than its second argument, an array element to test..

You should generally use qsort() before bsearch(), because the array should be sorted (should be in ascending order, ordered with the same criteria used by compare) before searching. This step is necessary because the binary search algorithm tests whether the search key is higher or lower than the middle element in the array, then eliminates half of the array, tests the middle of the result, eliminates half again, and so forth. If you define the comparison function for bsearch() with identical types for its two arguments, then qsort() can use the same comparison function.

The bsearch() function returns a pointer to an array element found that matches the search key. If no matching element is found, bsearch() returns a null pointer.^[a]

Example Use:

/* bsearch example */
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort, bsearch, NULL */

int compareints (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int values[] = { 50, 20, 60, 40, 10, 30 };

int main ()
{
  int * pItem;
  int key = 40;
  qsort (values, 6, sizeof (int), compareints);
  pItem = (int*) bsearch (&key, values, 6, sizeof (int), compareints);
  if (pItem!=NULL)
    printf ("%d is in the array.\n",*pItem);
  else
    printf ("%d is not in the array.\n",key);
  return 0;
}

Output:

40 is in the array.

In response to a comment below as to how to find the first element that is less/greater than key, here is a (probably dirty) workaround: you can iterate over the sorted array and compare its elements to key using the same compare function passed to this method, until you find an element less/greater than key.

I need help for binary search algorithm in C programming

You need to add return root or return tmp at the end of add.

binary search in Data Structure and Algorithm Analysis in C

If mid is 0, you want the line high = mid - 1; to set high to -1, which will cause the loop to stop.

If the variables were unsigned, high would wrap around to the maximum unsigned value which would cause a read past the end of the buffer and a likely crash.

As for for loops which count down, the following loop will never end:

for (unsigned i = START_VAL; i >= 0; i--) {...}  //WRONG

Because i is unsigned, the condition i >= 0 will always be true.

---

Related Topics