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, &search_uint64, compare_guint64, &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.)