1 /* 2 * Copyright (C) 2013 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package android.util; 18 19 class ContainerHelpers { 20 21 // This is Arrays.binarySearch(), but doesn't do any argument validation. binarySearch(int[] array, int size, int value)22 static int binarySearch(int[] array, int size, int value) { 23 int lo = 0; 24 int hi = size - 1; 25 26 while (lo <= hi) { 27 final int mid = (lo + hi) >>> 1; 28 final int midVal = array[mid]; 29 30 if (midVal < value) { 31 lo = mid + 1; 32 } else if (midVal > value) { 33 hi = mid - 1; 34 } else { 35 return mid; // value found 36 } 37 } 38 return ~lo; // value not present 39 } 40 binarySearch(long[] array, int size, long value)41 static int binarySearch(long[] array, int size, long value) { 42 int lo = 0; 43 int hi = size - 1; 44 45 while (lo <= hi) { 46 final int mid = (lo + hi) >>> 1; 47 final long midVal = array[mid]; 48 49 if (midVal < value) { 50 lo = mid + 1; 51 } else if (midVal > value) { 52 hi = mid - 1; 53 } else { 54 return mid; // value found 55 } 56 } 57 return ~lo; // value not present 58 } 59 } 60