二分查找易错和模板

Posted on In Views:

Java的二分查找源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int binarySearch(int[] a, int key) {
        return binarySearch0(a, 0, a.length, key);
    }

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
    }
    return -(low + 1);  // key not found.  //自己用的话可以把这个改成 return -1表示没有找到；
}

易错：必须加“=”

while循环里必须是low <= high，如果没有“=”,比如查找数组[3,4]中的4

low=0,high=1,mid=0

a[mid]=3<4

low=mid+1=1

导致循环直接结束而没有找到4