力扣704二分查找：思路分析+代码实现（递归与非递归）

叁歲伎倆 2024-04-24 14:36 4阅读 0赞

## 第一部分：题目 ##

🏠 链接：[704. 二分查找 - 力扣（LeetCode）][704. _ - _LeetCode]

⭐ 难度：简单

![46575befb810cb0f201d25fb84c8457b.png][]

## 第二部分：思路分析 ##

### 2.1 二分查找简介 ###

**二分查找**算法，也称**折半查找**算法，是一种在`有序数组`中查找某一特定元素的搜索算法。

### 2.2 二分查找思路分析 ###

1.  初始状态下，将整个序列作为搜索区域；
2.  找到搜索区域内的中间元素，和目标元素进行比对；
    
     *  如果相等，则搜索成功；
     *  如果中间元素大于目标元素，表明目标元素位于中间元素的左侧，将左侧区域作为新的搜素区域；
     *  反之，若中间元素小于目标元素，表明目标元素位于中间元素的右侧，将右侧区域作为新的搜素区域；
3.  重复执行第二步，直至找到目标元素。如果搜索区域无法再缩小，且区域内不包含任何元素，则表明整个序列中没有目标元素，查找失败。

### 2.3 算法描述 ###

<table> 
 <thead> 
 <tr> 
 <th>算法描述</th> 
 <th></th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>前提</td> 
 <td>给定一个内含 n n n 个元素的有序数组 A A A，满足 A 0 ≤ A 1 ≤ A 2 ≤ ⋯ ≤ A n − 1 A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1} A0≤A1≤A2≤⋯≤An−1，一个待查值 t a r g e t V a l u e targetValue targetValue</td> 
 </tr> 
 <tr> 
 <td>1</td> 
 <td>设置 l e f t = 0 left=0 left=0， r i g h t = n − 1 right=n-1 right=n−1</td> 
 </tr> 
 <tr> 
 <td>2</td> 
 <td>如果 l e f t &gt; r i g h t left \gt right left&gt;right，结束查找，没找到</td> 
 </tr> 
 <tr> 
 <td>3</td> 
 <td>设置 m i d = f l o o r ( l e f t + r i g h t 2 ) mid = floor(\frac {left + right}{2}) mid=floor(2left+right) ， m i d mid mid 为中间索引， f l o o r floor floor 是向下取整（ ≤ l e f t + r i g h t 2 \leq \frac {left+right}{2} ≤2left+right 的最小整数）</td> 
 </tr> 
 <tr> 
 <td>4</td> 
 <td>如果 t a r g e t V a l u e &lt; A m targetValue &lt; A_{m} targetValue&lt;Am 设置 r i g h t = m i d − 1 right = mid - 1 right=mid−1，跳到第2步</td> 
 </tr> 
 <tr> 
 <td>5</td> 
 <td>如果 A m i d &lt; t a r g e t V a l u e A_{mid} &lt; targetValue Amid&lt;targetValue 设置 l e f t = m i d + 1 left = mid + 1 left=mid+1，跳到第2步</td> 
 </tr> 
 <tr> 
 <td>6</td> 
 <td>如果 A m = t a r g e t V a l u e A_{m} = targetValue Am=targetValue，结束查找，找到了</td> 
 </tr> 
 </tbody> 
</table>

## 第三部分：代码实现 ##

### 3.1 🍀 基础版-查找范围区间左闭右闭 ###

/**
 * 二分查找基础版-查找范围区间左闭右闭
 *
 * @param nums 待查找的升序数组
 * @param target 待查找的目标值
 * @return 找到则返回目标值的索引，找不到返回-1
 */
 public int search(int[] nums, int target) {
 
 // 设置指针 left 指向数组的开始索引位置
 int left = 0;
 // 设置指针 right 指向数组的最后索引位置
 int right = nums.length - 1;
 
 // 定一个 mid，表示 left 和 right 的中间索引位置
 int mid;
 
 /*
 对 [left,right] 范围内的元素进行查找，left <= right 成立说明在 [left,right] 范围内还有元素可以可以查找
 while循环退出的两种方式：
 - 进入了 else，说明找到了，返回中间索引
 - 不满足 left <= right，说明范围不断缩小后依旧没有找到，退出循环
 */
 while (left <= right) {
 
 // 查找中间索引，如果 (left+right)/2 为小数则会自动向下取整
 mid = (left + right) / 2;
 
 if (target < nums[mid]) {
 
 // 如果 目标值 小于 中间索引值，说明 目标值索引 应该在 中间索引 的左边
 // 我们可以通过调整 right 的值缩小查找范围
 right = mid - 1;
 } else if (nums[mid] < target) {
 
 // 如果 目标值 大于 中间索引值，说明 目标值索引 应该在 中间索引 的右边
 // 我们可以通过调整 left 的值缩小查找范围
 left = mid + 1;
 } else {
 
 // 否则说明 目标值 等于 中间索引值，也就说明我们找到了
 return mid;
 }
 }
 
 // 走到这里说明没有进入过上面 while 中的else，while循环退出时 left > right
 // 说明没有找到
 return -1;
 }

### 3.2 🍀 基础版-查找范围区间左闭右开 ###

/**
 * 二分查找基础版-查找范围区间左闭右开
 *
 * @param nums 待查找的升序数组
 * @param target 待查找的目标值
 * @return 找到则返回目标值的索引，找不到返回-1
 */
 public int search(int[] nums, int target) {
 
 // 设置指针 left 指向数组的开始索引位置
 int left = 0;
 // 设置指针 right 指向查找范围的后一个索引位置
 // 在这里 right 只是作为一个边界，指向的一定不是查找目标。
 int right = nums.length;
 
 int mid;
 
 // 在 [left,right) 左闭右开的区间范围内进行目标值查找
 // 因为 right 只是一个边界不作为查找索引，因此不能将 left <= right 作为条件
 while (left < right) {
 
 
 mid = (left + right) >>> 1;
 
 if (target < nums[mid]) {
 
 // 目标值 小于 中间索引值，则应该将右范围缩小
 // 需要将查找范围变为 [left,mid)
 right = mid;
 } else if (nums[mid] < target) {
 
 left = mid + 1;
 } else {
 
 return mid;
 }
 }
 
 return -1;
 }

### 3.3 🍀 平衡版 ###

思想：

1.  左闭右开的区间，i 向的可能是目标，而 j 指向的不是目标
2.  不奢望循环内通过 m 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的（通过 i）
    
     *  j − i > 1 的含义是，在范围内待比较的元素个数 > 1
3.  改变 i 边界时，它指向的可能是目标，因此不能 m + 1
4.  循环内的平均比较次数减少了
5.  时间复杂度  Θ ( l o g ( n ) ) Θ(log(n)) Θ(log(n)) （最坏最好情况）

/**
 * <h3>二分查找平衡版</h3>
 *
 * <ol>
 * <li>不奢望循环内通过 m 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的(通过 i)</li>
 * <li>i 指针可能是查找目标</li>
 * <li>j 指针不可能是查找目标</li>
 * <li>因为 1. 2. 3. 当区域内还剩一个元素时, 表示为 j - i == 1</li>
 * <li>改变 i 边界时, m 可能就是目标, 同时因为 2. 所以有 i=m</li>
 * <li>改变 j 边界时, m 已经比较过不是目标, 同时因为 3. 所以有 j=m</li>
 * <li>三分支改为二分支, 循环内比较次数减少</li>
 * </ol>
 *
 * @param nums 待查找的升序数组
 * @param target 待查找的目标值
 * @return 找到则返回索引
 * 找不到返回 -1
 */
 public int search(int[] nums, int target) {
 
 int i = 0;
 int j = nums.length;
 
 // 范围内待查找的元素个数 > 1 时
 while (1 < j - i) {
 
 int m = (i + j) >>> 1;
 
 if (target < nums[m]) {
 
 // 目标在左边，缩小右边范围
 j = m;
 } else {
 
 // 目标在 m 或右边
 i = m;
 }
 }
 return (target == nums[i]) ? i : -1;
 }

### 3.4 🍀 递归实现 ###

public int search(int[] nums, int target) {
 
 return recurSearch(nums, target, 0, nums.length-1);
 }
 
 private int recurSearch(int[] nums, int target, int left, int right) {
 
 // 说明全部搜索完毕仍未找到
 if (left > right) {
 
 return -1;
 }
 // 得到中间索引
 int mid = (left + right) >>> 1;
 
 // 比较目标值与中间索引对应值的大小
 if (target < nums[mid]) {
 
 // 如果目标值小于中间值
 right = mid - 1;
 return recurSearch(nums, target, left, right);
 } else if (nums[mid] < target) {
 
 // 如果目标值大于中间值
 left = mid + 1;
 return recurSearch(nums, target, left, right);
 } else {
 
 // 说明相等，则返回
 return mid;
 }
 }

[704. _ - _LeetCode]: https://leetcode.cn/problems/binary-search/
[46575befb810cb0f201d25fb84c8457b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/ad0d4903abd1484799487300af4dfcee.png