无处不在的二分查找？
1 二分查找在实际中应用的很多，但是思想确实很简单，就是类似于分治的思想，比如你想从 1000 甚至更多的数字中寻找特定的数，如果你挨个去查找，当然可以，但是如果可以每次查找就可以确定想要查找的数不在另外一半中，是不是要快很多。
二分查找就是这么简单，只要记住，找到方法可以把范围缩小一半，就可以使用二分查找。
69 求开方
题目描述
给定一个非负整数，求它的开方，向下取整。
例子 1
输入: 8
输出: 2
解释: 8 的开方结果是 2.82842...，向下取整即是 2。
例子 2
输入: 4
输出: 2
解释: 4 的开方结果是 2。
说明
0 <= x <= 2^31 - 1
思考 1
这个思路很简单，因为是求 n 的开方，可以查找 1 到 n/2 的数字，这里就可以使用二分查找，如果发现等于 n，则返回，如果大于 n，则可以在比较小的一半中查找，如果发现小于 n，则可以在比较大的一半中查找
当然这个题目还有其他的数学解法，这里我们只是了解二分查找的思想，其他的数学解法，可以自己去了解。
实现 1
/** * @param {number} x * @return {number} */export default (x) => { const halfX = Math.ceil(x / 2); let low = 1; let high = halfX; while (low <= high) { let mid = Math.floor(low + (high - low) / 2); if (mid * mid === x) { return mid; } else if (mid * mid < x) { low = mid + 1; } else { high = mid - 1; } } return low * low > x ? low - 1 : low + 1;};
复制代码
复制代码
算法时间复杂度 O(lgn/2), 空间复杂度 O(1)
34 查找区间
题目描述
给定一个增序的整数数组和一个值，查找该值第一次和最后一次出现的位置。如果不存在该值，则两个返回值都设为-1
进阶
使用 O（lgn）时间复杂度解决。
例子 1
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
解释: 数字 8 在第 3 位第一次出现，在第 4 位最后一次出现。
例子 2
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
解释: 6 在数组中没有出现
例子 3
输入: nums = [3,3,3], target = 3
输出: [0,2]
解释: 3 在数组中出现第一次位置是 0，最后一次的位置 2
说明
1 0 <= nums.length <= 10^5
2 -10^9 <= nums[i] <= 10^9
3 -10^9 <= target <= 10^9
思考 1
这个思路很简单，因为数组是升序的，而且指明使用 O（lgn）方法解决，很明显使用二分查找解决。
这个也比较简单，就是常用的二分查找，如果最后没有发现，返回[-1,-1]就可以了
这里需要注意的就是你要找到 target 在数组中第一出现的位置和 target 最后一次出现的位置。
实现 1
/** * @param {number[]} nums * @param {number} target * @return {number[]} */export default (nums, target) => { if (nums.length === 0 || (nums.length === 1 && nums[0] !== target)) { return [-1, -1]; } if (nums.length === 1 && nums[0] === target) { return [0, 0]; }
const len = nums.length; let low = 0; let high = len - 1;
const res = []; while (low <= high) { // 为了防止数据溢出 let mid = Math.floor(low + (high - low) / 2);
if (nums[mid] === target) { let minFlag = false; let maxTemp = mid; let minTemp = mid; while (minTemp >= 0 && nums[minTemp] === target) { minTemp--; }
if (minTemp + 1 !== mid) { res.push(minTemp + 1); } else { res.push(mid); } while (maxTemp < len && nums[maxTemp] === target) { maxTemp++; }
if (maxTemp === mid + 1) { res.push(mid); } else { res.push(maxTemp - 1); } return res; } if (nums[mid] < target) { low = mid + 1; } if (nums[mid] > target) { high = mid - 1; } } if (res.length === 2) { return res.sort((a, b) => a - b); } else { return [-1, -1]; }};
复制代码
复制代码
算法时间复杂度 O(lgn), 空间复杂度 O(1)
81 旋转数组查找数字
题目描述
一个原本增序的数组被首尾相连后按某个位置断开(如 [1,2,2,3,4,5] → [2,3,4,5,1,2]，在第一 位和第二位断开)，我们称其为旋转数组。给定一个值，判断这个值是否存在于这个旋转数组中。如果存在返回 true，如果不存在返回 false
例子 1
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
例子 2
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
思考 1
最简单的肯定直接遍历数组，不过这里显然不使用这种
可以看到数组是一部分升序，另外一部分也是升序，问题是如何找到在哪里分割开？
当然这里可以遍历数组，找到分割开的两个升序数组，但是这样那不如直接遍历，不用二分查找了。
那么是否可以换个角度，假设我们如果直接使用二分查找，会怎么样呢？
可以想一下
刚开始我是想根据 mid 和 mid+1 的关系来决定移动 low 和 high 或者根据 mid 和 mid-1 的关系来决定移动 low 和 high，可是这样感觉逻辑很复杂
后来看了题解，才明白可以把 mid 和 low 和 high 的关系来移动指针，如果 nums[mid] 小于 nums[high],那肯定是升序，因为问的数组是升序的，如果 target 在这个升序数组中，那么就可以排除另一半了
当 nums[mid] 大于 nums[low]的时候，说明这也是一个派系数组，如果同时 target 在这个排序数组呢，同时也能排除另外一半数组了
这里还有另外一种情况，因为数组中存在重复的数字，如果发现 nums[mid]等于 num[low]，此时我们可以把 low++，重新计算 mid，计算 target 存在的范围
当 nums[mid]等于 num[high]，此时我们可以把 high，重新计算 mid，计算 target 存在的范围
但是运行之后，可以发现这里的二分查找和遍历数组使用时间基本差不多。
实现 1
/** * @param {number[]} nums * @param {number} target * @return {boolean} */export default (nums, target) => { if (nums.length === 0 || !nums) { return false; } if (nums.length === 1) return nums[0] === target;
let low = 0; let high = nums.length - 1; while (low <= high) { let mid = Math.floor(low + (high - low) / 2); if (nums[mid] === target) { return true; } if (nums[mid] < nums[high]) { // 判断target是否在这个范围内 if (target > nums[mid] && target <= nums[high]) { low = mid + 1; } else { high = mid - 1; } } else if (nums[mid] > nums[low]) { if (target >= nums[low] && target < nums[mid]) { high = mid - 1; } else { low = mid + 1; } } else if (nums[low] === nums[mid]) { low++; } else { high--; } } return false;};
复制代码
复制代码
算法时间复杂度 O(n),因为最坏的情况下，二分查找就变成了遍历数组了。 空间复杂度 O(1)
154 旋转数组查中寻找最小的元素
题目描述
假设一个排好序的数组在某处执行了一次“旋转”，找出最小的元素（数组元素可能重复），数组中包含重复数字
例子 1
输入: [1,3,5]
输出: 1
例子 2
输入: [2,2,2,0,1]
输出: 0
例子 3
输入: [3,3,1,3]
输出: 1
例子 4
输入: [10,1,10,10,10]
输出: 1
思考 1
这里和上面的 81 题目有点类似，应该可以采用同样的策略，只不过是把 81 的题目的 target 变成了最小的数字,思路基本类似。
另外说一下，这题在 leetcode 上标记为 hard，但是 81 题标记为 medium，但是两者的难度差不多，所以有时候，没有必要对题目的难度过于太在意
实现 1
/** * @param {number[]} nums * @return {number} */// 2, 2, 2, 0, 1;export default (nums) => { if (nums.length === 0 || !nums) { return false; } if (nums.length === 1) return nums[0]; let low = 0; let high = nums.length - 1; let min = Number.MAX_VALUE; while (low <= high) { let mid = Math.floor(low + (high - low) / 2); if (nums[mid] < nums[high]) { high = mid - 1; min = Math.min(nums[mid], min); } else if (nums[mid] > nums[low]) { min = Math.min(nums[low], min); low = mid + 1; } else if (nums[low] === nums[mid]) { min = Math.min(nums[low], min); low++; } else { min = Math.min(nums[high], min); high--; } } return min;};
复制代码
复制代码
算法时间复杂度 O(n),因为最坏的情况下，二分查找就变成了遍历数组了。 空间复杂度 O(1)
540. 有序数组中的单一元素
题目描述
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
例子 1
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
例子 2
输入: [3,3,7,7,10,11,11]
输出: 10
注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
思考 1
很简单，用二分查找就可以,要点就是因为数组中除了一个数字，其它的数字都是出现两次，所以可以根据 mid 的下标是奇数或者偶数来判断数字是否出现在那一侧
如果 mid 是偶数，那说明 low 到 mid 有奇数个数字，所以就可以判断 nums[mid] 和 nums[mid-1]是否相等，来判断只出现一次的数字是否出现在这一侧。
思路比较简单
实现 1
/** * @param {number[]} nums * @return {number} */
export default (nums) => { if (nums.length === 1) return nums[0]; let low = 0; let high = nums.length - 1; while (low <= high) { let mid = Math.floor(low + (high - low) / 2); console.log(low, high, mid); if ( (mid + 1 < nums.length && nums[mid] !== nums[mid + 1] && mid >= 1 && nums[mid] !== nums[mid - 1]) || (mid === nums.length - 1 && nums[mid] !== nums[mid - 1]) || (mid === 0 && nums[mid] !== nums[mid + 1]) ) { return nums[mid]; } if (mid % 2 !== 0) { if (mid >= 1 && nums[mid - 1] === nums[mid]) { low = mid + 1; } else { high = mid - 1; } } else { if (mid >= 1 && nums[mid] === nums[mid - 1]) { high = mid - 1; } else { low = mid + 1; } } } return nums[low];};
};
复制代码
复制代码
算法时间复杂度 O(lgn)。 空间复杂度 O(1)
4. 寻找两个正序数组的中位数
题目描述
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
例子 1
输入: nums1 = [1,3], nums2 = [2]
输出: 2.00000
解释：合并数组 = [1,2,3] ，中位数 2
例子 2
输入: nums1 = [1,2], nums2 = [3,4]
输出: 2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
例子 3
输入: nums1 = [0,0], nums2 = [0,0]
输出: 0.00000
例子 4
输入: nums1 = [], nums2 = [1]
输出: 1.00000
例子 5
输入: nums1 = [2], nums2 = []
输出: 2.00000
提示：
1 nums1.length == m
2 nums2.length == n
3 0 <= m <= 1000
4 0 <= n <= 1000
5 1 <= m + n <= 2000
6 -10^6 <= nums1[i], nums2[i] <= 10^6
思考 1
题目如果第一次见到，很难想出如何使用二分查找的，不过也可以思考试试
首先判断 nums1 和 nums2 的数组长度，让 nums1 的数组长度小于等于 nums2 的数组长度
假设 k 是 nums1 和 nums2 合并之后，我们要寻找的中位数下标，这里如果 nums1 和 nums2 合并后的长度是奇数，我们可以寻找 k = left 的数字
const left = Math.floor((nums1Len + nums2Len + 1) / 2)复制代码
复制代码
如果 nums1 和 nums2 合并后的长度是偶数，我们可以分别寻找合并后的数组中下标分别是下面这两个位置的，也就是寻找 k = left 和 k=right 两个位置的数字
const left = Math.floor((nums1Len + nums2Len + 1) / 2); const right = Math.floor((nums1Len + nums2Len + 2) / 2);复制代码
复制代码
原理很简单，我们先从 nums1 中拿出 k/2 个数字和从 nums2 中拿出 k/2 个数字，如果 nums1[k/2] 大于 nums2[k/2],那么我们要寻找的 k 位置的数字，肯定在 nums1 和 nums2 出去 0 到 k/2 的数组中。
因为 nums1[k/2]大于 nums2[k/2]，所以就可以排除 nums[k/2]之前的数字，但是我们不知道 nums1 的数字是否都大于 nums2[k/2]，所以可以在剩下的数组中寻找排在 k/2 位置的数字。
实现 1
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} */const getKth = (nums1, start1, end1, nums2, start2, end2, k) => { const len1 = end1 - start1 + 1; const len2 = end2 - start2 + 1; // 如果nums1的长度大于nums2的长度，改变两个数组的位置, 让数组长度最小的在前面，防止 // 这里的nums2[start2 + k - 1]报错 if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k); if (len1 === 0) return nums2[start2 + k - 1]; if (k === 1) return Math.min(nums1[start1], nums2[start2]);
const i = start1 + Math.min(len1, Math.floor(k / 2)) - 1; const j = start2 + Math.min(len2, Math.floor(k / 2)) - 1;
const nums1End = Math.min(end1, i + 1); const nums2End = Math.min(end2, j + 1); if (nums1[i] > nums2[j]) { return getKth(nums1, start1, nums1End, nums2, j + 1, end2, k - (j - start2 + 1)); } else { return getKth(nums1, i + 1, end1, nums2, start2, nums2End, k - (i - start1 + 1)); }};export default (nums1, nums2) => { if (nums1.length === 0 && nums2.length === 1) { return nums2[0]; } if (nums1.length === 1 && nums2.length === 0) { return nums1[0]; } const nums1Len = nums1.length; const nums2Len = nums2.length; // 分别找到奇数和偶数的中位数的左边和右边 const left = Math.floor((nums1Len + nums2Len + 1) / 2); const right = Math.floor((nums1Len + nums2Len + 2) / 2); // 如果是奇数，只寻找一次就可以了 if ((nums1Len + nums2Len) % 2 !== 0) { return getKth(nums1, 0, nums1Len - 1, nums2, 0, nums2Len - 1, left); } return ( (getKth(nums1, 0, nums1Len - 1, nums2, 0, nums2Len - 1, left) + getKth(nums1, 0, nums1Len - 1, nums2, 0, nums2Len - 1, right)) * 0.5 );};
复制代码
复制代码
算法时间复杂度也很容易理解
m 是 nums1.length，n 是 nums2.length 因为每次查找的范围都从(m+n)/2 缩小一半范围。所以时间复杂度是 O(lg(m+n))
空间复杂度 O(lg(m+n))
二分查找算法总结
二分查找其实就是一个分治思想，如果你可以根据一些条件，每次缩小一半的查找范围，基本就可以确定使用二分查找。
不过有些可能不是很明显，可能需要经过转化处理，不过核心就是可以不断的缩小查找范围，让我们离答案更近一下。
最后，还给大家整理出了一份面试宝典，有需要的只需要添加小编的 vx：mxzFAFAFA 即可免费领取！！！
评论