二、二分查找

只对有序的数组才能进行二分查找

• 通过不断更新 start 和 end 的值，进行 middle 数据的更新，从而找到数据

• 过程模拟

  • 每次查找都会将要查找的数与middle的值进行比较，从而确定下一个比较范围，最终找到数据

  

• 代码实现如下：

public class Main {
    public static void main(String[] args) {
        
        int[] arr = {1,4,12,34,67,87,99,124};
        int number = 99; // 要查找的数据

        int start = 0;
        int end = arr.length-1;
        int middle ;
        
        int count = 0; // 计数器，记录查找数据所需的次数
        
        while(start <= end){ // start 不可能大于 end
            count++;
            middle = (start + end)/2; // 每次循环都必须重新计算middle的值

            if (number < arr[middle]){ // 如果要查找的数 小于 中间值
                end = middle - 1; // 改变查找区间（start不变，end变为middle - 1的位置（middle位置数据已经比较过））
            }

            if (number > arr[middle]){ // 如果要查找的数 大于 中间值
                start = middle + 1; // 改变查找区间（start变为middle + 1的位置（middle位置数据已经比较过），end不变）
            }

            if (number == arr[middle]){ // 找到数据，结束循环
                System.out.println("数据" + number + "已找到！共查找了"+ count + "次！");
                return; 
            }
        }
        
        System.out.println("没有找到要查找的数据！");
    }
}