Java 实现二分法查找

二分法

public class BinarySearch {
    public static void main(String[] args) {
        int[] array = {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50};
        int target = 48;
        int idx = binarySearch(array, target);
        System.out.println(idx);
    }

    //二分法查找，找到返回元素索引，招不到返回-1
    public static int binarySearch(int[] a, int t){
        //l-左边 r-右边 m-中间
        int l = 0, r = a.length -1, m;
        while (l <= r) {
            //m = (l + r) / 2; //l+r结果数值过大会存在溢出
            m = (l + r) >>> 1; //正数右移运算相当于除二
            if(a[m] == t) {
                return m;
            }else if (a[m] > t){
                r = m - 1;
            }else {
                l = m + 1;
            }
        }
        return -1;
    }
}

输出结果

10

实现思路

• 1、前提：有已经排序的数组A(假设已经做好排序)
• 2、定义左边界L,右边界R,确定搜索范围，循环执行二分查找（3、4两步）
• 3、 获取中间索引 M = Floor((L+R)/2)
• 4、 中间索引的值 A[M]于待搜索的值T进行比较
  – 4.1 A[M] == T 表示找到，返回中间索引
  – 4.2 A[M] > T 中间值右侧的其他元素都大于T,无需比较，中间索引左边去找，M-1设置为右边界，重新查找
  – 4.3 A[M] < T 中间值左侧侧的其他元素都小于于T,无需比较，中间索引右边去找，M+1设置为左边界，重新查找
• 5 当L>R 时，表示没有找到，应结束循环。