g_array_binary_search in GLib 2.61.2

The final API so far in this mini-series on new APIs in the GLib 2.62 series is g_array_binary_search(), put together by Emmanuel Fleury and based on code by Christian Hergert. It’s due to be released in 2.61.2 soon. But first, a reminder about GLib version numbering.

Like the rest of GNOME’s official module set, GLib follows an odd/even versioning scheme, where every odd minor version number, like 2.61.x, is an unstable release building up to an even minor version number, like 2.62.x, which is stable. APIs may be added in unstable releases. They may be modified or even removed (if they haven’t been in a stable release yet). So all of the APIs I’ve blogged about recently still have a chance to be tweaked or dropped if people find problems with them. So if you see a problem or think that one of these APIs would be awkward to use in some way, please say, sooner rather than later! They need fixing before they’re in a stable release.

Back to today’s API, g_array_binary_search(). As its name suggests, this does a binary search on an array (which it requires is already sorted). You can use it like this:

static gint
compare_guint64 (gconstpointer a,
                 gconstpointer b)
{
  guint64 uint64_a = *((guint64 *) a);
  guint64 uint64_b = *((guint64 *) b);

  if (uint64_a < uint64_b)
    return -1;
  else if (uint64_a > uint64_b)
    return 1;
  else
    return 0;
}

g_autoptr(GArray) my_array = g_array_new (FALSE, TRUE, sizeof (guint64));

for (guint i = 0; i < 100; i++)
  {
    guint64 random_uint64 = ( (guint64) g_random_int () << 32) | g_random_int ();
    g_array_append_val (my_array, random_uint64);
  }

g_array_sort (my_array, compare_guint64);

/* Is ‘1234’ in the array? If so, where? */
const guint64 search_uint64 = 1234;
guint search_index;
if (g_array_binary_search (my_array, &amp;search_uint64, compare_guint64, &amp;search_index))
  g_message ("Found ‘1234’ at index %u", search_index);
else
  g_message ("Didn’t find ‘1234’");

As all computer science algorithms courses will tell you, a binary search is faster than a linear search, so you should use this in preference to iterating over an array to find an element in it, where possible.

(That’s not entirely true: the overheads of accounting for the binary search bounds, and the slowness of scattered memory loads from the array in a binary search vs sequential access in a linear search, will probably make it slower than a linear search for small arrays. But both will be fast, and if you need to care about that level of performance, you should be using a custom data structure rather than GArray.)

2 thoughts on “g_array_binary_search in GLib 2.61.2

  1. Alexander Patrakov

    One other case when a linear search may be faster than binary is when it is false that the searched-for thing can be found in all positions of the array with equal probability. I have hit this when trying to optimize an APE codec implementation - there, the searched-for element was in 0th or 1st position in the majority of cases, and was otherwise expected to be close to the beginning, so linear search (in a pre-sorted array) made sense.

    Reply
  2. Pingback: g_assert_finalize_object() in GLib 2.61.2 | drboblog

Leave a Reply to Alexander Patrakov Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.