二分查找

问题描述：

通过二分查找，查找数组中的某一个数值的位置（给定数组中的数值都不相等）。

算法实现：

public static int binarySearch(int[] arr, int key) {

    //数组必须是有序的
    int lo = 0;
    int hi = arr.length - 1;

    while (lo <= hi) {

        int mid = lo + (hi - lo) / 2;
        if(key < arr[mid]) {
            hi = mid - 1;
        } else if(key > arr[mid]) {
            lo = mid + 1;
        } else {
            return mid;
        }
    }

    return -1;

}

算法解析：

1.针对有序数组，设置最左边索引和最右边索引；

2.设置循环，当左边索引值不大于右边索引时查找，否则说明被查找的数据不在数组中，返回-1；

3.通过左右两个索引，计算中间索引，将中间索引对应的值和被查找的值进行比较；

4.根据步骤3中的比较结果，确定被查找的数是在中间索引的左边或者右边，或者就对应中间索引的值；

5.根据每次的比较，调整左右索引和中间索引，直到循环结束。

二分查找

原文：https://www.cnblogs.com/heibingtai/p/12615036.html