二分 #10
Description
Java Arrays.binarySearch()
内部实现是这样的：
private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
// 闭区间
int low = fromIndex;
int high = toIndex - 1;
// 当搜索区间不为空时
while (low <= high) {
// 使用算数右移来加速除法
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
// 到这里说明没有找到
// low是插入的位置 但是为了进行区分这里返回一个负数
// 之所以要+1是因为如果插入位置是0时，-low依然是0，无法告诉调用者是否找到
return -(low + 1); // key not found.
}这里采用的搜索方式是闭区间搜索，在找不到的情况下，最后一步之前一定是low == high，然后如果key比midVal大，说明插入位置要是mid+1，如果key比midVal小，插入位置是mid，刚好符合low的逻辑，所以low就是在key not found时的插入位置。