java：二分查找

80 阅读 0 评论 53 点赞

我是靠谱客的博主甜美含羞草，最近开发中收集的这篇文章主要介绍java：二分查找，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

备忘：官方API排序问题。

注意：调用binarySearch()方法前要先调用sort方法对数组进行排序，否则得出的返回值不定，这时二分搜索算法决定的。

	public static void binarySearch() {
		int[] a = new int[] { 4, 25, 10, 95, 06, 21 };
		System.out.println(Arrays.binarySearch(a, 95));
		
		Calendar.getInstance();
		Arrays.sort(a);
		System.out.println("排序后：" + Arrays.toString(a));
		System.out.println(Arrays.binarySearch(a, 95));
		System.out.println(Arrays.binarySearch(a, 101));
		System.out.println(Arrays.binarySearch(a, 2));
		System.out.println(Arrays.binarySearch(a, 4));
		System.out.println(Arrays.binarySearch(a, 11));
		System.out.println(Arrays.binarySearch(a, 101));
		System.out.println(Arrays.binarySearch(a, 10));
	}

return -(low + 1); // key not found.
之所以计算插入点值时索引要从1开始算，是因为-0=0，如果从0开始算，那么上面例子中关键字2和关键字4的返回值就一样了。

内存溢出
int mid = (low + high) / 2；low + high 是会溢出的。只要数组开的足够大，如1100000000。因此正确的解法是：int mid = (low + high) >>> 1无符号位移。
Can’t even compute average of two ints" is pretty embarrassing.

这里还有个问题：
为何无符号位移就可以避免溢出？

差1错误。
我们的左端点应该是当前可能区间的最小范围，那么右端点是最大范围呢，还是最大范围+1呢。我们取了中间值之后，在缩小区间时，有没有保持左右端点的这个假设的一致性呢？
死循环。我们做的是整数运算，整除2了之后，对于奇数和偶数的行为还不一样，很有可能有些情况下我们并没有减小取值范围，而形成死循环。

    // Like public version, but without range checks.
    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.
    }

参考资料：
[1]: https://blog.51cto.com/14233733/2369513
[2]:https://www.cnblogs.com/qingergege/p/5658292.html