二分查询

二分查询：

package com.cc;

/**
 * @Author: cc
 * @Create: 2021/12/20
 * 二分查询实现步骤：
 * 1.前提:有已排序数组A (假设已经做好)
 * 2.定义左边界L. 右边界R,确定搜索范围，循环执行二分查找(3. 4两步)
 * 3.获取中间索引 M= Flor((L+R) / 2) ==> 存在整数超出最大范围的问题，优化为移位运算：M = （L + R）>>> 1 ;
 * 4.中间索引的值 A[M]与待搜索的值T进行比较
 * A[M]== T表示找到，返回中间索引
 * A[M]> T,中间值右侧的其它元素都大于T,无需比较，中间索引左边去找，M- 1设置为右边界，重新查找
 * A[M] * 5.当L>R时, 表示没有找到，应结束循环
 */

public class BinarySearch {
    public static void main(String[] args) {
        int [] array = {1,3,5,6,12,53,65,77,98,123};
        int target = 53;
        int id = binarysearch(array,target);
        System.out.println(id);
    }
    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) >>> 1;//移位运算   >>> 1 相当于除以2
            if (a[m] == t){
                return m;
            }else if (a[m] < t){
                l = m + 1;
            }else {
                r = m - 1;
            }
        }
        return -1;
    }
}