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

Question

I cannot find any method implementing binary search. Is that because I failed to locate it, or is it because it doesn't exist?

_{I think the second, but I couldn't find a duplicate question, so maybe I am wrong.}

Magnuson

C doesn't have methods, only functions. – Blackdamp

I always thought that these two are synonymous, similarly to parameters and arguments.. – Magnuson

man -k search yields bsearch. (and many more) – Stambul

@Stambul I didn't know that flag, nice! I surfed the Internet and couldn't find an answer, thus my question - sorry if it appears silly! Lesson to be learned: sometimes the traditional methods work better 😉 – Magnuson

A Google search for [c binary search function] reveals #47321167 on the first page of results. – Prentice

I didn't use these search terms, so not for me @JimMischel. It could also be because I searched from a PC I had never used before, I don't know. – Magnuson

Answer 1

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.

Volteface

I used Yahoo, Google and Stack overflow search, and yet couldn't find it-awesome answer! I really hope that this post will help others, upvote it if you agree! – Magnuson

This function finds the occurrence of key in the array. Is there any way to find the first element less than key and/or the first element greater than key? – Pepe

@RishikeshRaje not if key does not occur in the array. Otherwise, you can use the next element (if there is one, and if key is unique - which it must be anyway). – Martyry

@WeatherVane there can be duplicates of the key on the array, so I don't see what you mean by it must be unique anyway. Except if I am misreading your comment. – Magnuson

@Magnuson I was going by the Visual C page which says If the array is not in ascending sort order or contains duplicate records with identical keys, the result is unpredictable. What I meant was that if the key is not unique the next lower, or greater key might not be adjacent. – Martyry

@WeatherVane, @gsamaras, this is why the array should be sorted in ascending order. In this case, it returns a pointer to the *first element that matches key. – Volteface

@WeatherVane if the array is not sorted, you cannot use binary search. If they are duplicates you can though. Is the reference of the Visual C applicable in standard C too? I hope not. – Magnuson

@Magnuson I am not querying the need to be sorted - that is obvious. I only meant that if there are duplicate keys, the next lower value (or greater) might not be the adjacent element. – Martyry

@Volteface the page I linked says bsearch returns a pointer to an occurrence of key. It does not say "the first" and a typical binary search won't always find the first occurrence if there are duplicate values. – Martyry

If you are searching for key and your array is sorted in ascending order, you get the first matching element. If key occurs, and you want to find the first element greater than key, a dirty solution would be to perform successive searches, each using the index returned by the previous search as a start point (base). – Volteface

@AA your link likewise does not say "the first" but "a matching element". – Martyry

The array has to be sorted in ascending order, that too is obvious. – Martyry

"The type size_t is defined in <stdlib.h> as unsigned int". Maybe on your system. On mine it's defined as long unsigned int in <stddef.h> and is double the size of unsigned int. – Zacharyzacherie

The info from that link is outdated; in c99 and later size_t is required to be defined in <sttdef.h>, and on ~90% of systems in use now size_t is 64bit and unsigned int is 32bit. – Zacharyzacherie

This is a terrble idea. Binary search is O(log n). Any binary search implementation could be easily modified to find the first elements greater than or equal to the search argument, preserving the O(log n) behavior. Searching the array from beginning to end is O(n). – Marcelinomarcell

Answer 2

The C library has a standard function bsearch, declared in <stdlib.h>, for exactly this purpose: locate a matching entry in a table of entries sorted in ascending order according to a given comparison function.

Here is the specification in the C Standard:

7.22.5.1 The bsearch function

Synopsis

#include <stdlib.h>
void *bsearch(const void *key, const void *base,
              size_t nmemb, size_t size,
              int (*compar)(const void *, const void *));

Description

The bsearch function searches an array of nmemb objects, the initial element of which is pointed to by base, for an element that matches the object pointed to by key. The size of each element of the array is specified by size.

The comparison function pointed to by compar is called with two arguments that point to the key object and to an array element, in that order. The function shall return an integer less than, equal to, or greater than zero if the key object is considered, respectively, to be less than, to match, or to be greater than the array element. The array shall consist of: all the elements that compare less than, all the elements that compare equal to, and all the elements that compare greater than the key object, in that order.³⁰⁸⁾

Returns

The bsearch function returns a pointer to a matching element of the array, or a null pointer if no match is found. If two elements compare as equal, which element is matched is unspecified.

---

_{308) In practice, the entire array is sorted according to the comparison function.}

This function has 2 shortcomings:

• if the table contains duplicate matching entries, it is unspecified which entry will be returned, as emphasised in the last paragraph above.
• the function cannot be used to locate the position where to insert the entry if it is not found in the table, it just returns a null pointer.

Here is a simple implementation that fixes the first point (it is coded to always return the matching entry closest to the beginning of the array) and can be modified to address the second:

#include <stdlib.h>

void *bsearch(const void *key, const void *base,
              size_t nmemb, size_t size,
              int (*compar)(const void *, const void *))
{
    const unsigned char *p;
    size_t m;
    int r;

    while (nmemb > 0) {
        m = (nmemb - 1) >> 1;
        p = (const unsigned char *)base + m * size;
        if ((r = compar(key, p)) < 0) {
            nmemb = m;
        } else
        if (r > 0) {
            base = p + size;
            nmemb -= m + 1;
        } else
        if (m == 0) {
            return (void *)p;
        } else {
            /* continue search to return first matching entry */
            nmemb = m + 1;
        }
    }
    // if you want the insertion point, you can return p here
    return NULL;
}

Marbles

Hi and thanks for upvoting my question! Are you sure about the duplicates issue? It would be nice to provide some reference. I couldn't find anything like this here cplusplus.com/reference/cstdlib/bsearch – Magnuson

@gsamaras: I updated the question with the specification from the C Standard that is explicit about duplicates: If two elements compare as equal, which element is matched is unspecified. – Marbles

You mean your answer:) Ah OK now I see what you mean, sure, I agree.. However, I had already upvoted your answer, so thanks again! :) – Magnuson