1/*
2 * Copyright 2014, NICTA
3 *
4 * This software may be distributed and modified according to the terms of
5 * the BSD 2-Clause license. Note that NO WARRANTY is provided.
6 * See "LICENSE_BSD2.txt" for details.
7 *
8 * @TAG(NICTA_BSD)
9 */
10
11/*
12 * Returns 1 iff the the element "v" is present in the sorted array "x" of
13 * length "n".
14 */
15unsigned binary_search(unsigned *x, unsigned n, unsigned v)
16{
17    unsigned l = 0;
18    unsigned r = n;
19    unsigned found = 0;
20
21    while (l < r && !found) {
22        unsigned m = (l + r) / 2;
23        unsigned d = x[m];
24        if (d == v) {
25            found = 1;
26        } else if (d < v) {
27            l = m + 1;
28        } else {
29            r = m;
30        }
31    }
32    return found;
33}
34
35