一、题目描述
给定一个数组，其采用如下代码定义：
int data[200];
for(i = 0 ; i < 200 ; i ++）data[i] = 4 * i + 6;
现给定某个数，请你求出它在 data 数组中的位置（下标）。
输入描述
输入一个待查找的整数（该整数一定在数组 data 中）。
输出描述
输出该整数在数组中的指标。
输入输出样例
示例 1
输入：
262
输出：
64
二、代码演示：
1.查询大于等于x的第一个数
import java.util.*;// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int[] data = new int[200];for(int i = 0 ; i < 200 ;i++){data[i] = 4 * i + 6;}int num = scan.nextInt();int l = 0;int r = 199;while(l < r){int mid = (l + r) / 2;if (num <= data[mid]) r = mid;else l = mid + 1;}System.out.print(l);scan.close();}
}2. 查询小于等于x的第一个数
while(l < r){int mid = (l + r + 1) / 2; //取中间位置靠右的数if (num < data[mid]) r = mid - 1;else l = mid ;}三、区别分析
这两种二分法的核心区别在于中间点选取策略和条件判断逻辑的不同，导致它们在特定场景下的行为差异：
1. 中间点计算方式
· 大于等于方法：mid = (l + r) / 2
选择中间靠左的索引（向下取整）。· 小于等于方法：mid = (l + r + 1) / 2
选择中间靠右的索引（向上取整），避免死循环。2. 条件判断逻辑
大于等于方法：
if (num <= data[mid]) { r = mid; } else { l = mid + 1; }
· 目标值 <= 中间值：收缩右边界 r 到 mid。
· 目标值 > 中间值：收缩左边界 l 到 mid + 1。
小于等于方法：
if (num < data[mid]) { r = mid - 1; } else { l = mid; }
· 目标值 < 中间值：收缩右边界 r 到 mid - 1。
· 目标值 >= 中间值：收缩左边界 l 到 mid。
3. 关键区别总结
特性 大于等于 小于等于 中间点选择 向下取整（靠左） 向上取整（靠右） 条件判断 num <= data[mid] 缩右边 num < data[mid] 缩右边，否则缩左边
4.原因分析
（1） 处理重复元素的效率
当数组中存在大量重复元素时：
· 第一种方法（左中位数）会收敛到第一个匹配项的位置。
· 第二种方法（右中位数）则会收敛到最后一个匹配项的位置。
示例：
数组 [2, 2, 2, 2]，目标值为 2：· 第一种方法最终返回 0（第一个 2）。
· 第二种方法最终返回 3（最后一个 2）。
（2） 避免死循环
在某些边界条件下，传统写法可能导致死循环。例如：
· 数组为 [1,3]，目标值为 2：
· 若采用 (l + r)/2 计算 mid，当 l=0、r=1 时：
· mid = 0，比较后发现目标值更大，l = mid + 1 = 1。
· 下一轮循环 l=1、r=1，循环结束，结果正确。
· 但如果初始条件或更新策略不当（如未调整边界），可能导致无限循环。
第二种方法通过强制向右取中间点（(l + r + 1)/2），避免了这一风险。
（3） 插入点的定义不同
· 第一种方法的目标是找到最左侧的插入点（即第一个大于等于目标值的元素的位置）。
· 第二种方法的目标是找到最右侧的插入点（即最后一个小于等于目标值的元素的位置加一）。
示例：
数组 [1,3,5,7,9]，目标值为 6：· 第一种方法返回 3（插入到 5 和 7 之间）。
· 第二种方法返回 2（错误，因为 5 < 6 <=7，正确插入点应为 3）。
（4） 适应不同的搜索条件
· 第一种方法适用于以下场景：
需要找到第一个满足条件的元素（如最小值、最早出现的元素）。
· 标准的二分查找模板（如 Java 的 Collections.binarySearch）。
· 第二种方法适用于以下场景：
需要找到最后一个满足条件的元素（如最大值、最后一次出现的元素）。
实现“找到最后一个小于等于目标值的元素”的需求。
（5） 性能与代码复杂性的权衡
· 第一种方法的代码更简洁，且在大多数情况下性能无差异。
· 第二种方法在重复元素较多时可以减少比较次数（直接跳过中间区域），但需额外注意边界条件。
总结
两种二分法的本质区别在于如何定义“成功条件”：
· 第一种方法关注左侧边界的收敛（向左缩进时保留可能的解）。
· 第二种方法关注右侧边界的收敛（向右缩进时保留可能的解）。
