#
跟着灵茶山艾府大佬学习算法思路的day3，目标是在一个月内掌握hot100
b站链接如下：
在排序数组中查找元素的第一个和最后一个位置 题目描述：
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
1
2
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
1
2
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
1
2
输入：nums = [], target = 0
输出：[-1,-1]
思路：
思路并不特殊，因为题目要求时间复杂度为O(log n) ，想到二分查找是比较自然的。对于区间的处理采用左闭右闭或者左开右开都可以（或者别的情况也可以），左闭右闭是二分查找比较典型的处理方式。
代码：
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
var searchRange = function(nums, target) {
const len = nums.length;
const div = (nums, target) => {
let left = 0;
let right = len - 1;
while (left <= right) {
// 当left跑到right的右边，说明就查找结束
let mid = Math.floor(left + (right - left) / 2);
// js的整数除运算不会默认向下取整
if (nums[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return left; // 此时left是target起点
}
let start = div(nums, target);
if (start === len || nums[start] !== target) {
return [-1, -1];
}
// 数组不存在等于target的数或起点值不等于target
let end = div(nums, target + 1) - 1;
// 可以查找到比 target 略大的数的前一个位置
return [start, end];
};
总结：
end 的计算方法的思路还是比较巧妙的，同时二分查找的边界判断也需要留心，不同的开闭区间会影响 left 或者 right 每次更新后的取值。还值得注意的一点是 js 的整数运算不会默认地向下取整，而是会出现浮点数，与 c/c++/java 不同。
寻找峰值 题目描述：
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
1
2
3
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
1
2
3
4
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
思路：
由于峰顶需要严格大于左右相邻值，所以一定在数组中，所以数组最右侧的元素一定是蓝色的，所以可以初始化左指针为0，右指针为n-2。
由于相邻的值严格不等，所以根据mid和mid+1的数值比较，就能知道当前的mid是在峰值左端还是右端，如果mid小于mid+1，那么mid在峰顶左端；如果mid大于mid+1，那么mid就是峰顶，或者在峰顶右端。
因为题目要求只要找到一个峰值，所以用二分一直判断mid与mid+1的关系即可。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var findPeakElement = function(nums) {
let len = nums.length;
let left = 0;
let right = len - 2; // len - 1同样可以解题，但len - 2会更好一些
while (left <= right) {
// 当left跑到right的右边，说明就查找结束
let mid = Math.floor(left + (right - left) / 2);
// js的整数除运算不会默认向下取整
if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return left; // 此时left是峰顶
};
总结：
视频里的解法是左开右开，我习惯于左闭右闭，就采用了左闭右闭的写法。这道题展示了二分查找的第二个用途，通过改变核心比较为nums[mid] 和 nums[mid+1]，可以在无序数组中寻找峰值。
二分查找的核心不是”有序”，而是通过特定条件的设置，每次能排除一半的搜索空间。