### String binary search in Zig

Zig has a generic `std.sort.binarySearch`

function that can be used to performance a binary search on an already-sorted array. In order for it to work, you have to provide a function that compares two values and returns an `std.math.Order`

.

This is very easy to use for integers, but takes a bit more effort for strings. This is something I needed in order to check if a username was reserved.

Here's the function you'll pass to `binarySearch`

:

```
fn compareString(_: void, key: []const u8, value: []const u8) std.math.Order {
var key_compare = key;
var value_compare = value;
var result = std.math.Order.eq;
// Force both values to the same length so we can figure out if key is gt or lt value on a character by character basis.
if (value.len < key.len) {
result = std.math.Order.gt;
key_compare = key[0..value.len];
} else if (value.len > key.len) {
result = std.math.Order.lt;
value_compare = value[0..key.len];
}
for (key_compare, value_compare) |k, v| {
var order = std.math.order(k, v);
if (order != .eq) {
return order;
}
}
return result;
}
```

The important thing to note about the above is that we *cannot* short-circuit based on the string length. Yes, if the `key`

and `value`

are different lengths, they obviously aren't equal, but we aren't just after equal or not equal, we need to know if key is less than or greater than value and that requires comparing each character until we find one that isn't equal.

Here's how you'd use the above function:

```
const name = "leto";
const reserved_usernames = [_][]const u8 {"about", "home", "privacy", "support"};
// binarySearch returns ?usize, the index of the found result, if any
if (std.sort.binarySearch([]const u8, username, &reserved_usernames, {}, compareString) != null) {
// username is reserved, error!
}
```

#### Leave a Comment

All comments are reviewed before being made public.