Java 算法之二分查找

二分查找找某个数值

前提：数组已经排好序

求该值所在数组中的位置

二分查找实现步骤

1.需排好序的数组

2.定义左边界L,右边界R，确定搜索范围，循环执行二分查找（3，4步骤）

3.获取中间索引 M=(L+R)/2

4.中间索引的值 arr[M] 与待搜索值T 进行比较

arr[M]=T 表示已经找到
arr[M]>T 表示中间值的右侧其他元素都大于T 无需比较，中间索引左边去找，M-1设置为右边界，重新查找
arr[M]<T 表示中间值的左侧其他元素都小于T 无需比较，中间索引右边去找，M+1设置为左边界，重新查找

5.当L>R时表示没有找到跳出循环

代码实现如下:

private static int binarySearch(int[] arr,int T) {
    int L=0;
    int R= arr.length-1;
    int M;
    while (L <= R) {

        M = (L + R) / 2;
        if (arr[M] == T) {
            return M;
        } else if (arr[M] > T) {
            R = M - 1;
        } else {
            L = M + 1;
        }

    }

    return -1;

}

以上算法个小问题，即当L R 数很大时，会出现数据溢出问题

如：

int R =Interger.MAX_VALUE-1;

int L=0;

M=(R+L)/2

当在右侧时

L=M+1

M=(L+R)/2

此时 M 溢出为负数

解决方法1：

（L+R)/2 可转换为： L/2+R/2 ==> L-L/2+R/2 ==> L+（R/2-L/2）==>L+(R-L)/2

private static int binarySearch(int[] arr,int T) {
    int L=0;
    int R= arr.length-1;
    int M;
    while (L <= R) {

        M = L+(R-L)/2;
        if (arr[M] == T) {
            return M;
        } else if (arr[M] > T) {
            R = M - 1;
        } else {
            L = M + 1;
        }

    }

    return -1;

}

解决方法2：

（L+R)/2 转换为无符号右移（>>>）（L+R）>>>1


  private static int binarySearch(int[] arr,int T) {
    int L=0;
    int R= arr.length-1;
    int M;
    while (L <= R) {

        M = (L+R)>>> 1;
        if (arr[M] == T) {
            return M;
        } else if (arr[M] > T) {
            R = M - 1;
        } else {
            L = M + 1;
        }

    }

    return -1;

}