云林县网站建设_网站建设公司_AJAX_seo优化

一、什么是 Binary Search（二分查找）

1.1 基本思想

二分查找的核心思想非常简单：

在一个有序序列中，每次都将搜索区间缩小一半

具体过程：

1. 取中间元素mid
2. 比较key与mid：
   • 相等 → 查找成功
   • 小于 → 去左半部分
   • 大于 → 去右半部分
3. 重复直到找到或区间为空

1.2 时间复杂度

• 时间复杂度：O(log n)
• 空间复杂度：O(1)（迭代实现）

这也是二分查找被广泛使用的原因。

如果想深入了解二分查找的思想，推荐看【力荐】分享丨【算法题单】二分算法（二分答案/最小化最大值/最大化最小值/第K小） - 讨论 - 力扣（LeetCode），详细介绍了二分查找的思想，干货很多，在实战中慢慢掌握。

二、Java 中的 binarySearch 在哪里？

Java 中主要有两类 binarySearch 实现：

三、Arrays.binarySearch 详解（最常用）

3.1 基本方法签名

publicstaticintbinarySearch(int[]a,intkey)

还有大量重载版本，例如：

binarySearch(long[]a,longkey)binarySearch(double[]a,doublekey)binarySearch(T[]a,Tkey)binarySearch(T[]a,Tkey,Comparator<?superT>c)binarySearch(int[]a,intfromIndex,inttoIndex,intkey)

3.2 最简单示例

int[]arr={1,3,5,7,9};intindex=Arrays.binarySearch(arr,5);System.out.println(index);// 2

✔ 返回的是元素所在的下标

四、⚠️ 使用 binarySearch 的前提条件（非常重要）

❗ 数组必须是“有序的”

int[]arr={5,1,9,3};Arrays.binarySearch(arr,3);// 结果是 ❌ 不确定的

binarySearch 不会帮你排序

如果数组无序，返回结果是“未定义行为”

正确用法：

Arrays.sort(arr);Arrays.binarySearch(arr,3);

五、binarySearch 的返回值规则（重点 & 易错）

5.1 找到元素

返回>=0的整数（元素索引）

示例：

int[]arr={10,20,30};Arrays.binarySearch(arr,20);// 1

5.2 没找到元素（很多人不懂）

返回-(插入点)-1

5.2.1 什么是插入点？

插入点 =保持数组有序时，该元素应该插入的位置

示例：

int[]arr={10,20,30,40};intr=Arrays.binarySearch(arr,25);System.out.println(r);// -3

解释：

• 25 应该插入到 index = 2
• 返回值 =-(2) - 1 = -3

5.2.2 为什么不直接返回插入点？

这是一个很好的问题！Java没有直接返回插入点，而是采用-(插入点)-1的设计，主要有以下几个重要原因：

①.清晰区分两种状态

// 如果直接返回插入点：int[]arr={1,3,5,7,9};intresult1=binarySearch(arr,5);// 返回2intresult2=binarySearch(arr,4);// 也返回2？// 问题：怎么区分是"找到了5"还是"4应该插入到2"？// 需要额外检查，或者用特殊值标记

②.避免歧义和特殊值冲突

如果直接返回插入点：

• 元素找到时返回索引
• 元素未找到时也返回索引
• 无法区分这两种情况

例如，在索引0找到元素 vs 应该插入到索引0：

int[]arr={10,20,30};intresult1=binarySearch(arr,10);// 如果直接返回0intresult2=binarySearch(arr,5);// 也应该返回0// 完全无法区分！

③.现有设计的优势

使用负值可以：

• 一目了然：看到负数就知道没找到
• 无歧义：正数索引只表示找到的位置
• 信息完整：同时包含了"是否找到"和"插入位置"

intindex=Arrays.binarySearch(arr,key);if(index>=0){// 肯定找到了System.out.println("找到，位置："+index);}else{// 肯定没找到intinsertPoint=-index-1;System.out.println("未找到，应插入到："+insertPoint);}

④.对比其他方案

方案A：返回特殊值（如-1表示未找到）

// 问题：丢失插入位置信息intindex=binarySearch(arr,key);if(index==-1){// 知道没找到，但不知道插哪里}

方案B：返回对象/Pair

classSearchResult{booleanfound;intposition;// 找到的位置或插入位置}// 问题：Java 8之前没有内置Pair，创建对象开销大

方案C：通过参数返回（C++风格）

intbinarySearch(int[]arr,intkey,IntHolderinsertPoint){// 问题：API复杂，需要额外参数}

⑤.数学上的优雅性

-(插入点)-1的设计很巧妙：

• 所有插入点 ≥ 0，所以-(插入点)-1 ≤ -1
• 因此任何index ≥ 0都只能是找到的情况
• 转换公式简单可逆

⑥.实际应用场景

这种设计特别适合维护有序集合：

// 在有序列表中插入元素，保持有序List<Integer>list=newArrayList<>(Arrays.asList(1,3,5,7,9));intkey=4;intindex=Collections.binarySearch(list,key);if(index<0){list.add(-index-1,key);// 直接使用转换后的插入位置}// 结果是 [1, 3, 4, 5, 7, 9]

⑦.与历史设计的兼容性

Java的集合框架（TreeSet、TreeMap等）内部大量使用这种模式：

// TreeMap.put()内部类似这样的逻辑intcmp=compare(key,currentKey);if(cmp<0){// 左子树}elseif(cmp>0){// 右子树}else{// 找到，替换值}

5.3 通用公式

if(result>=0){// 找到了，result 是索引}else{intinsertPoint=-result-1;}

六、对象数组与 Comparator 版本

6.1 对象数组（Comparable）

String[]arr={"apple","banana","cherry"};intindex=Arrays.binarySearch(arr,"banana");

⚠️ 前提：

• 元素必须实现Comparable
• 排序规则与查找规则一致

6.2 使用 Comparator

Arrays.binarySearch(arr,key,comparator)

示例：

Arrays.sort(arr,Comparator.comparingInt(String::length));intidx=Arrays.binarySearch(arr,"pear",Comparator.comparingInt(String::length));

❗排序用的 Comparator 必须和 binarySearch 用的一致

七、Collections.binarySearch（List 版本）

7.1 方法签名

publicstatic<T>intbinarySearch(List<?extendsComparable<?superT>>list,Tkey)

或：

publicstatic<T>intbinarySearch(List<?extendsT>list,Tkey,Comparator<?superT>c)

7.2 示例

List<Integer>list=Arrays.asList(1,3,5,7,9);intindex=Collections.binarySearch(list,7);// 3

⚠️ 对LinkedList不友好（内部会转为索引访问）

八、binarySearch 的源码思想（简化版）

以int[]为例（伪代码）：

intlow=0;inthigh=a.length-1;while(low<=high){intmid=(low+high)>>>1;intmidVal=a[mid];if(midVal<key)low=mid+1;elseif(midVal>key)high=mid-1;elsereturnmid;}return-(low+1);

下图为java.util.Arrays;包中的源码

设计亮点

• >>> 1防止整数溢出，也可以使用low+(high-low)/2来表示
• 返回插入点信息，方便后续逻辑

九、性能与适用场景分析

坑点避免

❌ 数组没排序就 binarySearch
❌ 排序规则和 Comparator 不一致
❌ 误以为返回 -1 表示没找到
❌ 在 LinkedList 上频繁调用