二分查找

1.二分查找概念

给定一个数组，经过排序后，从中间开始查找。
如果查找到的中间值比target大，则原数组右边的值舍弃；
反之，舍弃左边的值；依次寻找。
举个例子(假设数组已经排好序)：

int[] a = {1,2,3,4,5,6,7,8,9};
//target表示需要寻找的数字
target = 3；

第一次找到的值为5，因为5>3，故舍弃右边的值。
a数组变成{1,2,3,4}，此时取2，因为2<3，故舍弃左边的值。
a数组变成{3,4}，此时取3，target = 3，查找结束。

2. 编程思路

1 有序数组
2 定义左边界L，右边界R，确定搜索范围，循环执行二分查找。
3 获取中间索引 M = Floor（L+R）/ 2
4 中间索引值与A[M]与待搜索的值T进行比较
 ① A[M] = T表示找到，返回中间索引
 ② A[M] < T，中间值左侧的其他元素都小于T，无须比较，M+1设置为左边界，重新查找
 ③ A[M] > T，中间值右侧的其他元素都大于T，无须比较，M-1设置为右边界，重新查找
5 当L > R时，表示没有找到，结束循环。

3.代码实现

package array;

import java.util.Arrays;

/**
 * @author: 邹祥发
 * @date: 2021/10/11 22:39
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] array = {1, 5, 8, 6, 11, 2};
        //数组排序
        Arrays.sort(array);
        int target = 6;
        int index = binarySearch(array, target);
        System.out.println(index);
    }

    //二分查找，找到返回元素索引，找不到返回-1
    public static int binarySearch(int[] a, int t) {
        int l = 0, r = a.length - 1, m;
        while (l <= r) {
            m = (l + r) / 2;
            if (a[m] == t) {
                return m;
            } else if (a[m] < t) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return -1;
    }
}

输出结果：3

4.越界问题

如果R = Integer.MAX_VALUE - 1;
且目标值在中间值的右侧，此时
L = M + 1，M = (L + R) / 2会产生越界。
如何解决？
方法一：
因为（L + R）/ 2 ==> L/2 + R/2 ==> L + (-L/2 + R/2)
所以当 M = L + (-L/2 + R/2) 时，不会产生越界。
方法二：
使用位运算。
将M = (L + R) / 2改成 M = (L + R) >>> 1。

5.改进后的代码

package array;

import java.util.Arrays;

/**
 * @author: 邹祥发
 * @date: 2021/10/11 22:39
 * 二分查找
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] array = {1, 5, 8, 6, 11, 2};
        //数组排序
        Arrays.sort(array);
        int target = 6;
        int index = binarySearch(array, target);
        System.out.println(index);
    }

    //二分查找，找到返回元素索引，找不到返回-1
    public static int binarySearch(int[] a, int t) {
        int l = 0, r = a.length - 1, m;
        while (l <= r) {
            //m = (l + r) / 2;
            //解决数组越界，提高执行效率
            m = (l + r) >>> 1;
            if (a[m] == t) {
                return m;
            } else if (a[m] < t) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return -1;
    }
}