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