力扣704二分查找：思路分析+代码实现（递归与非递归）
第一部分：题目
🏠 链接：704. 二分查找 - 力扣（LeetCode）
⭐ 难度：简单
第二部分：思路分析
2.1 二分查找简介
二分查找算法，也称折半查找算法，是一种在有序数组中查找某一特定元素的搜索算法。
2.2 二分查找思路分析
- 初始状态下，将整个序列作为搜索区域；
- 找到搜索区域内的中间元素，和目标元素进行比对；
- 如果相等，则搜索成功；
- 如果中间元素大于目标元素，表明目标元素位于中间元素的左侧，将左侧区域作为新的搜素区域；
- 反之，若中间元素小于目标元素，表明目标元素位于中间元素的右侧，将右侧区域作为新的搜素区域；
- 重复执行第二步，直至找到目标元素。如果搜索区域无法再缩小，且区域内不包含任何元素，则表明整个序列中没有目标元素，查找失败。
2.3 算法描述
| 算法描述 | |
|---|---|
| 前提 | 给定一个内含 nnn 个元素的有序数组 AAA，满足 A0≤A1≤A2≤⋯≤An−1A_{0}\\leq A_{1}\\leq A_{2}\\leq \\cdots \\leq A_{n-1}A0≤A1≤A2≤⋯≤An−1，一个待查值 targetValuetargetValuetargetValue |
| 1 | 设置 left=0left=0left=0，right=n−1right=n-1right=n−1 |
| 2 | 如果 left>rightleft \\gt rightleft>right，结束查找，没找到 |
| 3 | 设置 mid=floor(left+right2)mid = floor(\\frac {left + right}{2})mid=floor(2left+right) ，midmidmid 为中间索引，floorfloorfloor 是向下取整（≤left+right2\\leq \\frac {left+right}{2}≤2left+right 的最小整数） |
| 4 | 如果 targetValue<AmtargetValue < A_{m}targetValue<Am 设置 right=mid−1right = mid - 1right=mid−1，跳到第2步 |
| 5 | 如果 Amid<targetValueA_{mid} < targetValueAmid<targetValue 设置 left=mid+1left = mid + 1left=mid+1，跳到第2步 |
| 6 | 如果 Am=targetValueA_{m} = targetValueAm=targetValue，结束查找，找到了 |
第三部分：代码实现
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 🍀 平衡版
思想：
- 左闭右开的区间，i 向的可能是目标，而 j 指向的不是目标
- 不奢望循环内通过 m 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的（通过 i）
- j − i > 1 的含义是，在范围内待比较的元素个数 > 1
- 改变 i 边界时，它指向的可能是目标，因此不能 m + 1
- 循环内的平均比较次数减少了
- 时间复杂度 Θ(log(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 <p>找到则返回索引</p>* <p>找不到返回 -1</p>*/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;}}
