二分查找算法c语言分析（一点就透的二分查找算法）
二分查找算法c语言分析（一点就透的二分查找算法）这个思路很简单，因为是求n的开方，可以查找1到n/2的数字， 这里就可以使用二分查找，如果发现等于n，则返回，如果大于n，则可以在比较小的一半中查找，如果发现小于n，则可以在比较大的一半中查找说明0 <= x <= 2^31 - 1输入: 8输出: 2解释: 8 的开方结果是 2.82842...，向下取整即是 2。例子2输入: 4输出: 2解释: 4 的开方结果是 2。
1 二分查找在实际中应用的很多，但是思想确实很简单，就是类似于分治的思想，比如你想从1000甚至更多的数字中寻找特定的数，如果你挨个去查找，当然可以，但是如果可以每次查找就可以确定想要查找的数不在另外一半中，是不是要快很多。
二分查找就是这么简单，只要记住，找到方法可以把范围缩小一半，就可以使用二分查找。
69 求开方题目描述给定一个非负整数，求它的开方，向下取整。
例子1
输入: 8
输出: 2
解释: 8 的开方结果是 2.82842...，向下取整即是 2。
例子2
输入: 4
输出: 2
解释: 4 的开方结果是 2。
说明
0 <= x <= 2^31 - 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
这个思路很简单，因为数组是升序的，而且指明使用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
最简单的肯定直接遍历数组，不过这里显然不使用这种
可以看到数组是一部分升序，另外一部分也是升序，问题是如何找到在哪里分割开？
当然这里可以遍历数组，找到分割开的两个升序数组，但是这样那不如直接遍历，不用二分查找了。
那么是否可以换个角度，假设我们如果直接使用二分查找，会怎么样呢？
可以想一下
刚开始我是想根据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
这里和上面的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
题目如果第一次见到，很难想出如何使用二分查找的，不过也可以思考试试
首先判断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))
二分查找其实就是一个分值思想，如果你可以根据一些条件，每次缩小一半的查找范围，基本就可以确定使用二分查找。
不过有些可能不是很明显，可能需要经过转化处理，不过核心就是可以不断的缩小查找范围，让我们离答案更近一下。
