1-1二分查找

二分查找（Binary Search）是一种高效的搜索算法，适用于已经排好序的数组。它通过将待查找的元素与数组中间的元素进行比较，从而每次可以排除掉一半的元素，以此来快速缩小搜索范围，直到找到目标元素或确定其不存在于数组中。该算法的时间复杂度为$O(logn)$，意味着随着输入规模的增长，查找时间增长缓慢

---

1 基础版

需求：在有序数组$A$中查找值$target$。

• 如果找到，则返回该值在数组中的索引。
• 如果未找到，则返回$-1$。

1.1 算法描述

1. 初始化：给定一个内含$n$个元素的有序数组$A$，满足$A_0\le A_1\le A_2\le ...\le A_{n-1}$，一个待查值$target$。
2. 设置初始索引：设置$i=0$，$j=n-1$。
3. 终止条件：如果$i>j$，结束查找，找不到需要的值，返回$-1$。
4. 计算中间索引：设置$m=\lfloor \frac{i+j}{2}\rfloor$，$m$为数组的中间索引，$\lfloor \cdot \rfloor$表示向下取整。
5. 比较并调整索引：
   • 如果$target<A_m$，设置$j=m-1$，跳转至第2步。
   • 如果$A_m<target$，设置$i=m+1$，跳转至第2步。
   • 如果$A_m=target$，结束查找，并返回所在位置的数组索引$m$。

1.2 算法流程图

1.3 算法实现

1.3.1 Java实现

这是一种最简单的二分查找算法的实现，从逻辑上没什么问题，但是在实际应用的过程中是可能会出bug的。

/*** 使用二分查找算法在一个有序数组中查找目标值的基本实现** @param arr    一个有序的整数数组* @param target 要查找的目标值* @return 目标值在数组中的索引，如果目标值不在数组中，则返回-1*/
public static int binarySearchBasic(int[] arr, int target) {// TODO 1. 设置初始索引int left = 0; // 左边界int right = arr.length - 1; // 右边界// TODO 2. 循环查找while (left <= right) {// TODO 2.1. 计算中间索引int mid = (right + left) >>> 1;// TODO 2.2. 比较中间索引的值与目标值if (arr[mid] == target) {// TODO 2.3. 如果等于目标值，返回中间索引return mid;} else if (arr[mid] < target) {// TODO 2.4. 如果小于目标值，更新左边界left = mid + 1;} else {// TODO 2.5. 如果大于目标值，更新右边界right = mid - 1;}}// TODO 3. 如果循环结束，没有找到目标值，返回-1return -1;
}

1. 循环条件为左边界≤右边界
   • 循环条件 left <= right 保证了以下两种情况：
     • 当区间仍有元素时（left <= right），继续检查。
     • 当区间为空时（left > right），终止循环。
   • 若循环条件为 left < right：
     • 问题场景：当区间仅剩一个元素时（left == right），循环条件不成立，直接跳过检查。
     • 后果：若该元素恰好是目标值，算法会错误地返回 -1。
   • 正确条件 left <= right：
     • 覆盖所有有效区间：即使只剩一个元素（left == right），仍会进入循环检查。
     • 终止条件正确性：当 left > right 时，区间已为空，表明目标值不存在。
2. 中间索引如何求

   • (right + left) / 2

     这一种是直接计算中间值的方法

     计算方式在数学上是正确的，但是这种方法存在一个严重的潜在问题：整数溢出。

     • 当 left 和 right 都接近 int 类型的最大值（Integer.MAX_VALUE，即 2^31 - 1）时，left + right 可能会超过 int 类型的最大值，导致溢出。
     • 溢出后，计算结果会变成负数，导致 mid 的值错误，进而引发索引越界或逻辑错误。

   • left + (right - left) / 2

     这一种是通过偏移量计算中间值的方法

     • 避免溢出：right - left 的结果一定小于 right，不会超过 int 的范围。
     • 逻辑清晰：通过偏移量计算中间值，更直观地表达“从 left 开始，加上区间长度的一半”。

   • 使用 >>（有符号右移）

     >> 是有符号右移操作符，它会保留符号位（即最高位），并在左侧补上与符号位相同的位。

     int mid = (left + right) >> 1;
     

     • 特点
       • 等价于除以 2：(left + right) >> 1 等价于 (left + right) / 2。
       • 保留符号位：如果 left + right 是负数，右移后结果仍然是负数。
       • 性能优化：右移操作比除法操作更快，适合对性能要求较高的场景。
     • 潜在问题
       • 整数溢出：如果 left + right 超过 int 的最大值（Integer.MAX_VALUE），仍然会导致溢出问题。
       • 负数问题：如果 left + right 是负数，右移结果可能与预期不符。相加为负数的原因是：当两个正数相加的结果超过 int 的最大值时，最高位（符号位）会从 0 变为 1，导致结果被解释为负数。

   • 使用 >>>（无符号右移）

     >>> 是无符号右移操作符，它会忽略符号位，并在左侧补 0。

     int mid = (left + right) >>> 1;
     

     • 特点
       • 等价于除以 2：(left + right) >>> 1 等价于将 left + right 视为无符号整数后除以 2。
       • 忽略符号位：无论 left + right 是正数还是负数，右移后结果都是正数。
       • 避免负数问题：即使 left + right 是负数，结果也会被正确处理。
     • 优点
       • 避免溢出问题：>>> 可以正确处理 left + right 超过 int 最大值的情况。
         • 例如，left = 1_500_000_000，right = 2_000_000_000，left + right 会溢出为负数，但 (left + right) >>> 1 会得到正确的结果。
       • 性能优化：与 >> 类似，右移操作比除法更快。

   • 性能对比

     以下是几种计算方式的性能对比：

     计算方式	性能	是否可能溢出	是否支持负数
     (left + right) / 2	较慢	是	是
     left + (right - left) / 2	较慢	否	是
     (left + right) >> 1	较快	是	是
     (left + right) >>> 1	较快	否	是

---

2 改动版

需求：在有序数组$A$中查找值$target$，通过左闭右开区间优化边界处理。

• 如果找到，则返回该值在数组中的索引。
• 如果未找到，则返回$-1$。

2.1 算法描述

1. 初始化：给定一个内含$n$个元素的有序数组$A$，满足$A_0\le A_1\le A_2\le ...\le A_{n-1}$，一个待查值$target$。
2. 设置初始索引：设置$i=0$，$j=n$（左闭右开区间）。
3. 终止条件：如果$i\ge j$，结束查找，返回$-1$。
4. 计算中间索引：设置$m=\lfloor \frac{i+j}{2}\rfloor$。
5. 比较并调整索引：
   • 如果$target<A_m$，设置$j=m$（保持右开特性）。
   • 如果$A_m<target$，设置$i=m+1$。
   • 如果$A_m=target$，返回索引$m$。

2.2 算法流程图

2.3 算法实现

2.3.1 Java实现

/*** 使用二分查找算法查找目标值在数组中的索引* 如果目标值存在于数组中，则返回其索引；如果目标值不存在于数组中，则返回-1* 二分查找算法的前提是输入数组必须是有序的** @param arr    一个有序的整数数组* @param target 目标值* @return 目标值在数组中的索引，如果目标值不存在于数组中，则返回-1*/
public static int binarySearchAlternative(int[] arr, int target) {// TODO 1. 设置初始索引int left = 0; // 左边界int right = arr.length; // 右边界// TODO 2. 循环查找while (left < right) {// TODO 2.1. 计算中间索引int mid = (right + left) >>> 1;// TODO 2.2. 比较中间索引的值与目标值if (arr[mid] == target) {// TODO 2.3. 如果等于目标值，返回中间索引return mid;} else if (arr[mid] < target) {// TODO 2.4. 如果小于目标值，更新左边界left = mid + 1;} else {// TODO 2.5. 如果大于目标值，更新右边界right = mid;}}// TODO 3. 如果循环结束，没有找到目标值，返回-1return -1;
}

2.4 改进点分析

2.4.1 区间定义差异

特性	基础版	改进版
初始区间	左闭右闭 [0, n-1]	左闭右开 [0, n)
循环条件	left <= right	left < right
右边界更新方式	right = mid - 1	right = mid

2.4.2 核心改进原理

1. 右开区间的优势：
   • 更直观的索引计算：初始右边界直接取数组长度，无需-1调整
   • 减少边界条件判断：当right = mid时，天然保持右开特性
2. 循环次数优化：
   • 基础版终止条件为left > right，需要多一次无效循环
   • 改进版终止条件为left == right，精确控制循环次数

2.4.3 数学等价性证明

对于区间长度$L=j-i$：

• 基础版每次迭代减少$L/2$
• 改进版每次迭代减少$\lceil L/2\rceil$

两种方式时间复杂度均为$O(\log n)$，但改进版具有更好的空间局部性

---

3 平衡版

3.1 算法描述

1. 初始化：给定一个内含 $n$ 个元素的有序数组 $A$，满足 $A_0\le A_1\le A_2\le ...\le A_{n-1}$，一个待查值 $target$。
2. 设置初始索引：设置左边界$left=0$，右边界$ right=n$（左闭右开区间）。
3. 终止条件：如果 $right-left\le 1$，结束查找，返回 $-1$。
4. 计算中间索引：设置$ mid=\lfloor \frac{i+j}{2} \rfloor$。
5. 比较并调整索引：
   • 如果 $target<A_{mid}$，设置 $right=mid$。
   • 如果 $A_{mid}<target$，设置$ left=mid$。
   • 如果 $A_{mid}=target$，返回索引$ mid$。

3.2 算法流程图

3.3 算法实现

3.3.1 Java实现

/*** 使用平衡二分查找算法在已排序的数组中搜索指定目标值* 此方法通过不断缩小搜索范围的一半来高效查找目标值，适用于大规模数据集** @param arr    已排序的整数数组，不包含重复元素* @param target 要搜索的目标值* @return 目标值在数组中的索引；如果目标值不在数组中，则返回-1*/
public static int binarySearchBalanced(int[] arr, int target) {// 1. 设置初始索引int left = 0; // 左边界int right = arr.length; // 右边界// 2. 循环查找while (1 < right - left) {// 2.1. 计算中间索引int mid = (right + left) >>> 1;// 2.2. 比较中间索引的值与目标值if (arr[mid] < target) {// 2.4. 如果小于目标值，更新左边界left = mid;} else {// 2.5. 如果大于目标值，更新右边界right = mid;}}// 3. 最后检查左边界是否为目标值if (arr[left] == target) {// 3.1 如果等于目标值，返回左边界return left;} else {// 3.2 如果没有找到目标值，返回-1return -1;}
}

3.4 改进点分析

3.4.1 区间定义差异

特性	基础版	平衡版
初始区间	左闭右闭$ [0, n-1]$	左闭右开$ [0, n)$
循环条件	left <= right	1 < right - left
右边界更新方式	right = mid - 1	right = mid

3.4.2 核心改进原理

1. 右开区间的优势：
   • 更直观的索引计算：初始右边界直接取数组长度，无需 -1 调整。
   • 减少边界条件判断：当 right = mid 时，天然保持右开特性。
2. 循环次数优化：
   • 基础版终止条件为 left > right，需要多一次无效循环。
   • 平衡版终止条件为 1 < right - left，精确控制循环次数。

3.4.3 数学等价性证明

对于区间长度$L=j-i$：

• 基础版每次迭代减少$L/2$。
• 平衡版每次迭代减少$\lceil L/2\rceil$。

两种方式时间复杂度均为$O(logn)$，但平衡版具有更好的空间局部性。

3.4.4 性能分析

• 时间复杂度：$O(logn)$。每次迭代将搜索范围缩小一半，因此查找效率非常高。
• 空间复杂度：$O(1)$。算法只使用了常量级别的额外空间，适合大规模数据集。

4 对比总结

4.1 区间定义

版本	初始区间	循环条件	右边界更新方式
基础版	左闭右闭$[0,n-1]$	left <= right	right = mid - 1
改进版	左闭右开$ [0, n)$	left < right	right = mid
平衡版	左闭右开$ [0, n)$	right - left > 1	right = mid

4.2 中间索引计算

• 基础版：int mid = (left + right) >>> 1;
• 改进版：int mid = (left + right) >>> 1;
• 平衡版：int mid = (left + right) >>> 1;

4.3 终止条件

• 基础版：当循环结束时，若未找到目标值，返回$-1$。
• 改进版：当循环结束时，若未找到目标值，返回$-1$。
• 平衡版：循环结束后，检查左边界是否为目标值。

4.4 改进点

• 基础版：逻辑简单，易于理解。
• 改进版：
  • 使用左闭右开区间，右边界更新更直观。
  • 使用无符号右移运算符 >>> 计算中间值，避免整数溢出。
• 平衡版：
  • 通过左闭右开区间和特定的终止条件，进一步优化循环次数。
  • 最后检查左边界，减少不必要的比较。

4.5 性能分析

• 时间复杂度：
  • 所有版本均为$ O(log n)$，但在实际运行中，平衡版的循环次数更少，性能稍优。
• 空间复杂度：
  • 所有版本均为$ O(1)$，不占用额外空间。