35.2 二分查找

二分查找要先排序，再查找

package com.itheima.d8_sort_binarysearch;
/**
 * 目标：理解二分搜索的原理并实现
 */
public class Test2 {
    public static void main(String[] args) {
        // 1.定义数组   // 使用二分查找要先排序
        int[] arr = {10,14,16,18,20,22,24,26,28};
        System.out.println(binarySearch(arr, 28));
    }
    /**
     * 二分查找算法的实现
     * @param arr  排序的数组
     * @param data 要找的数据
     * @return 索引， 如果元素不存在，直接返回-1
     */
    // 使用二分查找，最好是定义成方法
    public static int binarySearch(int[] arr, int data){
        // 1. 定义左边位置  和  右边位置
        int left = 0;
        int right = arr.length - 1;  // 获取右边最后一个元素的索引
        // 2. 开始循环，折半查询
        while (left <= right){
            // 取中间索引
            int middleIndex = (left + right) / 2; // 不精确没关系，差不多中间位置即可
            // 3. 判断当前中间位置的元素和要找的元素的大小情况
            if (data > arr[middleIndex]) {
                // 如果要找的数据元素，大于 中间索引
                // 则往右边找，左边位置更新为 = 中间索引 + 1 . 加完1 后 执行上面的代码left <= right再次比较
                left = middleIndex + 1;
            }else if (data <  arr[middleIndex]){
                // 如果要找的元素 小于中间元素
                // 则往左边找 ， 右边位置更新为 = 中间索引 - 1   减完1 后 执行上面的代码left <= right再次比较
                right = middleIndex -1;
            }else {
                // 当要找到数据元素等于中间元素，则直接返回
                return middleIndex;
            }
        }
        // 当都没有找到时：返回-1
        return -1;
    }
}