二分查找

计算前提：
 
- 数组包含100万个元素（n = 1,000,000）
- 假设目标元素一定存在于数组中
- 目标元素等概率出现在任意位置
 
计算过程：
 
- 如果目标在第1个位置：需要1次比较
- 如果目标在第2个位置：需要2次比较
- ...
- 如果目标在第1,000,000个位置：需要1,000,000次比较
 
平均比较次数 = (1 + 2 + 3 + ... + n) ÷ n  
= [n × (n+1) ÷ 2] ÷ n  
= (n+1) ÷ 2  
= (1,000,000 + 1) ÷ 2  
= 500,000.5 ≈ 50万次比较

计算前提：
- 数组包含100万个元素且已排序
 
计算过程：
 
- 设k为需要的比较次数
- 每次比较后，搜索范围变为原来的一半
- 经过k次比较后，搜索范围大小为：1,000,000 ÷ 2^k
- 当搜索范围≤1时，查找结束：1,000,000 ÷ 2^k ≤ 1
- 即：2^k ≥ 1,000,000
 
求解k：
k = log₂(1,000,000) ≈ 19.93
 
由于比较次数必须是整数，向上取整得到 20次比较。

public static int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 避免整数溢出
        
        if (arr[mid] == target) {
            return mid;  // 找到目标，返回索引
        } else if (arr[mid] < target) {
            left = mid + 1;  // 目标在右半部分
        } else {
            right = mid - 1;  // 目标在左半部分
        }
    }
    
    return -1;  // 未找到目标
}

public static int lowerBound(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    int result = arr.length;  // 初始化为数组长度，表示所有元素都小于目标值
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] >= target) {
            result = mid;
            right = mid - 1;  // 继续在左半部分查找
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}

public class StudentScoresSearch {
    public static void main(String[] args) {
        // 假设有一个已排序的10000个学生成绩数组
        int[] scores = new int[10000];
        // 实际应用中这里应该加载真实数据
        
        int targetScore = 85;
        int resultIndex = binarySearch(scores, targetScore);
        
        if (resultIndex != -1) {
            System.out.println("找到了得分为85分的学生，索引位置: " + resultIndex);
        } else {
            System.out.println("没有学生得到85分");
        }
        
        // 说明：在10000个元素的数组中，二分查找最多只需14次比较(log₂10000≈14)
    }
    
    // 这里插入上面定义的binarySearch方法
}