无处不在的二分查找？
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)
- 有序数组中的单一元素
题目描述
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
例子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)
- 寻找两个正序数组的中位数
题目描述
给定两个大小为 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))
二分查找算法总结
二分查找其实就是一个分治思想，如果你可以根据一些条件，每次缩小一半的查找范围，基本就可以确定使用二分查找。
不过有些可能不是很明显，可能需要经过转化处理，不过核心就是可以不断的缩小查找范围，让我们离答案更近一下。
网友评论