1 2 /* 3 * Copyright 2010 Google Inc. 4 * 5 * Use of this source code is governed by a BSD-style license that can be 6 * found in the LICENSE file. 7 */ 8 9 10 11 #ifndef GrTBSearch_DEFINED 12 #define GrTBSearch_DEFINED 13 14 template <typename ELEM, typename KEY> 15 int GrTBSearch(const ELEM array[], int count, KEY target) { 16 GrAssert(count >= 0); 17 if (0 == count) { 18 // we should insert it at 0 19 return ~0; 20 } 21 22 int high = count - 1; 23 int low = 0; 24 while (high > low) { 25 int index = (low + high) >> 1; 26 if (LT(array[index], target)) { 27 low = index + 1; 28 } else { 29 high = index; 30 } 31 } 32 33 // check if we found it 34 if (EQ(array[high], target)) { 35 return high; 36 } 37 38 // now return the ~ of where we should insert it 39 if (LT(array[high], target)) { 40 high += 1; 41 } 42 return ~high; 43 } 44 45 #endif 46
