跟着灵茶山艾府大佬学习算法思路的day4，目标是在一个月内掌握hot100
b站链接如下：
寻找旋转排序数组中的最小值 题目描述：
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2] - 若旋转
7次，则可以得到[0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
1
2
3
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
1
2
3
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
1
2
3
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
思路：
同样是寻找划分二分的条件，这里考虑用数组最后的值，由于最小值一定在数组中，所以最后的数组值要么是最小值，要么在最小值右侧，所以这题也可以在0到n-2之间二分。
如果mid小于最后一个数，那么会有两种可能，它在一段递增数组中，或者在两段递增数组的第二段，无论是什么情况，mid对应的值要么是最小值，要么也在最小值右侧。
另一种情况就是mid大于最后一个数，那么mid一定不可能在只有一段递增序列的数组中，且在两段递增数组中，一定是第一段较长，也就是说mid一定位于第一段，mid一定在最小值左侧。
值得注意的是，最小值一定是和最后一个数在同一段上的。
代码：
思路1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var findMin = function(nums) {
let len = nums.length;
let left = 0;
let right = len - 1;
while (left <= right) {
// 当left跑到right的右边，说明就查找结束
let mid = Math.floor(left + (right - left) / 2);
// js的整数除运算不会默认向下取整
if (nums[mid] > nums[len - 1]) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return nums[left]; // 此时left是最小值
};
思路2：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var findMin = function(nums) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
let mid = Math.floor(left + (right - left) / 2);
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return nums[left];
};
总结：
思路1和思路2唯一的区别就是if条件不同，一个是nums[mid] > nums[len - 1]，一个是nums[mid] > nums[right]。nums[right]在这题中具备的性质是与nums[len - 1]类似的，因为right 收缩过程中，在最后一次循环，left跑到right后面之前，nums[right] 始终 ≤ nums[len-1]，且两者在同一段。
如果是154. 寻找旋转排序数组中的最小值 II，就只能采用nums[right]，因为此时左段和右段的界限会因为有重复值而不再清晰，例如当最后的元素与mid元素值相等时。
寻找旋转排序数组中的最小值 II 的解题代码附如下，这道题是困难题，边界条件需要注意的判断较多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var findMin = function(nums) {
let left = 0;
let right = nums.length - 2; // 初始化为n-2
while (left <= right) {
let mid = Math.floor(left + (right - left) / 2);
if (nums[mid] > nums[right + 1]) { // 与right+1比较
left = mid + 1;
} else if (nums[mid] < nums[right + 1]) {
right = mid - 1;
}
else { // 排除相同元素
right--;
}
}
return nums[left];
};
153 用
left < right+right = mid，退出时left == right必然是答案，所以nums[right]作为比较基准没问题。154 引入了
right--，必须把nums[n-1]固定为比较基准，踢出搜索空间，才能保证right--不会把答案推出去，所以用right + 1。三件事必须配套：
while (left <= right)+right = mid - 1+nums[right + 1]。换掉任何一个都会破坏平衡。
搜索旋转排序数组 题目描述：
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
1
2
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
1
2
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
1
2
输入：nums = [1], target = 0
输出：-1
思路：
这道题有两个思路，一个是通过两次二分，第一次查找到最小值（因为最小值区分了左右两段），然后比较target以及nums[mid]和最后一个数的大小，来决定在哪一边进行二次二分。
也有一次二分的方法，因为通过比较target和nums[mid]和最后一个数的大小关系，是能够得知target和mid目前所处位置是第一段还是第二段的，所以就能得到如下的三种二分条件关系：
如果 x 和 target 在不同的递增段：
如果 target 在第一段，x 在第二段，说明 target 在 x 的左边。 如果 x 在第一段，target 在第二段，说明 target 在 x 的右边。 如果 x 和 target 在相同的递增段：
和 正常的二分一样，比较 x 和 target 的大小即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
var search = function(nums, target) {
let left = 0;
let right = nums.length - 1;
const last = nums[nums.length - 1];
while (left <= right) {
let mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
return mid;
}
const midInFirst = nums[mid] > last; // mid 是否在第一段
const targetInFirst = target > last; // target 是否在第一段
if (midInFirst !== targetInFirst) {
// 不同段时看 target 在哪段
if (targetInFirst) {
right = mid - 1; // target 在第一段，mid 在第二段，target 在左
} else {
left = mid + 1; // mid 在第一段，target 在第二段，target 在右
}
} else {
// 同段时正常二分
if (target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
return -1;
};
总结：
这题自己没啥思路，感觉挺难，总体上是基于灵神的思路去做的。