目录
什么是二分查找
二分查找
题目链接
题目描述
思路分析
代码实现
在排序数组中查找元素的第一个和最后一个位置
题目链接
题目描述
思路分析
代码实现
x 的平方根
题目链接
题目描述
思路分析
代码实现
二分小结
山脉数组的峰顶索引
题目链接
题目描述
思路分析
代码实现
寻找旋转排序数组中的最小值
题目链接
题目描述
思路分析
代码实现
点名
题目链接
题目描述
思路分析
代码实现
什么是二分查找
二分查找是一种高效的搜索算法，适用于在一组数据中中查找某个特定元素，其基本思路是通过不断将查找范围减半来快速定位目标元素
接下来，我们就通过具体的问题，来学习二分查找
二分查找
题目链接
704. 二分查找 - 力扣（LeetCode）
题目描述
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums= [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1
提示：
- 你可以假设
nums中的所有元素是不重复的。 -
n将在[1, 10000]之间。 -
nums的每个元素都将在[-9999, 9999]之间。
思路分析
题目要求我们在 升序 数组 nums 中查找值为 target 的元素，若存在，返回该元素下标；若不存在，返回 -1
最简单的方法，就是使用 暴力枚举，遍历数组，判断每一个元素是否等于 target，若等于，则返回该下标值；若不等于，继续遍历。当遍历完数组仍未找到时，就返回 -1，此时的时间复杂度为 O(N)
但此时我们并没有利用到 数组是升序 的这个特性
在示例2中：
当遍历到 3 时，还是没有找到 target，但此时元素的值已经大于 target 了，由于数组是升序的，因此，后面的元素也都是大于 target 的，没有必要再继续遍历
此时，我们就可以进行优化：
遍历数组，判断每一个元素是否等于 target，若等于，则返回该下标值；若小于，继续遍历；若大于，直接返回 -1
再尝试进行优化：
当我们判断出 nums[i] 的值大于 target 时，直接就将 nums[i] 后面元素舍弃了，但当 nums[i] 小于 target 时，由于是从前向后进行遍历的，因此，每次都只舍弃了一个元素
若我们在数组中随机选取一个元素：
若 nums[i] 小于 target，说明 [0, nums[i] ] 区间内的元素（也就是 nums[i] 及其左边的元素）都小于 target，都可以直接舍弃，此时，我们就直接舍弃了一个区间内的元素，而不是一个元素
而若 nums[i] 等于 target，说明当前元素就是要找的值，直接返回下标即可
若 nums[i] 大于 target，说明 [ nums[i], nums.length - 1 ] 区间内的元素（也就是 nums[i] 及其右边的元素）都大于 target，都可以直接舍弃，此时，我们也直接舍弃了一个区间的元素
此时，我们就通过 nums[i] 将这个数组划分成了两个区间： [0, nums[i] 和 [ nums[i], nums.length - 1 ]
当 nums[i] 等于 target 时直接返回
当 nums[i] 小于 target 时，舍弃左边区间的元素
当 nums[i] 大于 target 时，舍弃右边区间的元素
那么，要如何确定 i 的位置呢？
在每次舍弃一个区间的元素时，我们都希望能够去掉更多的元素，但是我们并不能确定 nums[i] 和 target 的大小关系，因此，
若 左区间 > 右区间，舍弃右区间时舍弃的元素较少
若 左区间 < 右区间，舍弃左区间时舍弃的元素较少
因此，让 左区间 = 右区间，这样，无论舍弃左区间还是右区间，都能去掉一半的元素
也就是 让 i 处于中间位置
接着，要如何找到这个中间位置呢？
要找到中间位置就需要知道左端点和右端点的位置，因此，定义 left 和 right 指针，分别指向区间的左端点和右端点，然后通过 left 和 right 计算出中点 mid 的位置，从而将数组划分为两个区间
然后根据 nums[mid] 的值进行判断：
若 nums[mid] = target，说明 nums[mid] 就是要找的元素，直接返回 mid 的值即可
若 nums[mid] > target，说明 [mid, right] 区间内的元素都大于 target，直接舍弃，继续在左边区间[left, mid - 1]进行查找，即 right = mid - 1，然后再继续查找
若 nums[mid] < target，说明 [left, mid] 区间内的元素都小于 target，直接舍弃，继续在右边区间 [mid + 1, right] 进行查找，即 left = mid + 1，然后继续查找
当 [left，right] 区间内元素个数为偶数时，此时，中间位置会有两个元素
在本题中，选取中间左边元素来划分区间 或 选取中间右边元素来划分区间都可以
选取中间左边元素来划分区间，左边区间内元素会比右边区间内元素少1
同理， 选取中间右边元素来划分区间，右边区间内元素会比左边区间内元素少1
但并不会影响查找过程
最后，什么时候结束循环呢？
当 [left, right] 区间中只有一个元素时（也就是 left = right = mid），此时，仍需要判断这个元素是否等于 target，若不等于，则会移动 left 或 right，此时 left > right，区间不再存在，说明找不到值为 target 的元素，此时需要退出循环
因此，循环的结束条件为 left > right
在本题中，我们根据 数组升序 这个特性，选取了 中间元素，将数组划分为了两个区间，再通过 nums[mid] 和 target 的大小关系，选择性地舍弃了一部分元素，进而继续在另一部分区间内继续查找
上述查找方法也就是二分查找：
找到某个规律，选取某个元素将这个数组划分为两部分，根据规律选择性地舍弃一部分元素，进而继续在另一部分区间内继续查找
那么，二分查找的时间复杂度是多少呢？
数组的大小为 n，最坏情况下查找了x 次
第一次查找后，剩余 n / 2 （
）个元素
第二次查找后，剩余 n / 4（
） 个元素
第三次查找后，剩余 n / 8 （
）个元素
...
第 x 次查找后，剩余 1（
） 个元素
x = 
因此，二分查找的时间复杂度为 
接下来，我们就来尝试编写代码，解决问题
代码实现
class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
int left = 0, right = len - 1;
while (left <= right) {
int mid = (left + right) / 2;
if(nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
return mid;
}
}
return -1;
}
}在排序数组中查找元素的第一个和最后一个位置
题目链接
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
题目描述
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]
示例 2：
输入： nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]
示例 3：
输入：nums = [], target = 0 输出：[-1,-1]
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109-
nums是一个非递减数组 -109 <= target <= 109
思路分析
题目要求我们在非递减数组 nums 中找到 target 出现的开始位置和结束位置，若不存在 target，则返回 [-1, -1]
最简单的方法就是遍历数组，找到 target 的开始和结束位置，但题目要求我们使用 时间复杂度为 O(log n) 的算法解决此问题
数组是非递减的，也就是有序的，因此，我们仍可以考虑使用二分查找，来解决本题：
根据数据的非递减性，将其划分为两个区间，然后舍去某个区间，进而在另一个区间查找
题目要求我们找到 target 出现的开始位置和结束位置
我们首先来找开始位置
同样的，我们还是使用 left 和 right 分别标记区间的左端点和右端点，然后求 mid
再判断 target 和 mid 的值
若 nums[mid] < target，表明 [left, mid] 区间内的所有元素都小于 target，不是我们要找的值，因此，都可以舍去，即 left = mid + 1
若 nums[mid] = target，此时直接返回吗？
当然不能，要找的是 target 出现的第一个位置，而mid 位置可能并不是第一个位置：
就如同上图所示，此时 mid 位置并不是 target 出现的第一个位置，但 mid 位置也可能是 target 出现的第一个位置，此时，并不能判断出 mid 是否为 target 出现的第一个位置，因此，不能直接返回，还要继续进行查找
但是，由于 nums[mid] = target，则 [mid + 1, right] 区间的值都大于等于 target，不是我们要找的第一个位置，因此，可以舍去[mid + 1, right] 区间内的所有元素，即 right = mid
若 nums[mid] > target， 表明[mid + 1, right] 区间内的元素都大于 target，不是我们要找的位置，因此，可以直接舍去，即 right = mid - 1
由于 nums[mid] = target 和 nums[mid] > target 的情况下，都会舍去右边区间[mid + 1, right] 的元素，因此，我们可以合并这两种情况，即 nums[mid] >= target，此时，可以舍去[mid + 1, right] 区间内的元素，即 right = mid
不能舍去 mid 位置的值，因为当 nums[mid] = target 时，该位置可能为 target 出现的第一个位置，因此不能舍去，还是通过后续的查找进行判断
当 [left，right] 区间内元素个数为偶数时，此时，中间位置会有两个元素
此时，我们应该选取哪个元素来划分区间呢？
我们要找到是 target 出现的第一个位置，此时，需要选择 中间左边元素 进行区间划分
若中间两个元素值相同，且都为 target
此时，我们选择左侧元素能够去掉更多的元素
此外，最重要的是，若我们选择选择右边元素划分区间，可能会出现死循环的情况
当我们在移动 left 和 right 时，
若 nums[mid] < target，left = mid + 1，left 向后移动，区间一定会缩小
若 nums[mid] >= target，right = mid，此时区间可能不会缩小
例如：
此时若我们选择 右边元素 来划分区间：
nums[mid] = target，right = mid，然后继续判断 nums[mid] = target，right = mid...
left、right 和 mid 的值不会改变，也就陷入了死循环
因此，在 [left, right] 区间内元素个数为偶数时，要选择中间左边元素进行区间划分，也就是在寻找中间元素时要向下取整（mid = (left + right) / 2）
那么，循环什么时候结束呢？
left = right 为循环的结束条件，而不是 left > right
当 left = right 时，若数组中存在 target ，则此时 left（或 right）的位置就为 target 出现的第一个位置
若 继续判断，则会陷入死循环
当 left = right 时，mid = left = right，此时区间内只有一个元素，mid 位置的值一定大于等于 target，此时，若还要继续判断，则 right = mid，区间大小不会改变，left、right 和 mid 的位置不会改变，也就会一致循环判断下去，陷入死循环
总结一下寻找 target出现的第一个位置的思路：
（1）定义 left 和 right，指向区间的左端点和右端点，通过 left 和 right 确定 mid 的位置，当有两个中间元素时，要选取左边的中间元素，即 mid = (left + right) / 2
（2）判断 nums[mid] 和 target 的大小关系
若 nums[mid] < target，[left, mid] 区间内的元素都可以舍弃，left = mid + 1
若 nums[mid] >= target，[mid + 1, right] 区间内的元素可以舍弃，right = mid
（3）继续判断，直到 left = right
接下来，我们就继续找到 target 出现的最后一个位置
使用 left 和 right 分别标记区间的左端点和右端点，然后求 mid
判断 target 和 mid 的值：
若 nums[mid] > target，则 [mid, right] 区间内（mid 及右边元素）的所有元素都大于 target，不是我们要找的值，因此，都可以舍去，即 right = mid - 1
若 nums[mid] <= target，则 [left, mid - 1] 区间内（mid 左边元素）的元素都小于等于 target，不是我们要找的值，都可以舍弃，即 left = mid
不能舍弃 mid ，mid 可能是要找的最后一个位置，因此不能舍弃，mid 还需要参与后续的判断
同样，当 [left，right] 区间内元素个数为偶数时，此时，中间位置会有两个元素
此时，我们需要选择 中间右边位置 的元素来划分区间，若我们选中中间左边元素来划分区间，可能会出现死循环
若 nums[mid] > target，right= mid - 1，right 向前移动，区间一定会缩小
若 nums[mid] <= target，left = mid，此时区间可能不会缩小
如上图所示，此时 nums[mid] = target，left = mid，区间并不会缩小，left、right 和 mid 的位置并不会改变
因此，要选取中间右边元素来划分区间，也就是向上取整（mid = (left + right + 1) / 2）
循环什么时候结束呢？
同样，left = right 为循环的结束条件，而不是 left > right
当 left = right 时，mid = left = right，此时区间内只有一个元素，mid 位置的值一定小于等于 target，此时，若还要继续判断，则 left = mid，区间大小不会改变，left、right 和 mid 的位置不会改变，也就会一致循环判断下去，陷入死循环
因此，当 left = right 时，循环结束，此时 left = right = mid，
若 target 存在，该位置就是 target 的结束位置，或是不存在 target
总结一下寻找 target出现的第一个位置的思路：
（1）定义 left 和 right，指向区间的左端点和右端点，通过 left 和 right 确定 mid 的位置，当有两个中间元素时，要选取右边的中间元素，即 mid = (left + right + 1) / 2
（2）判断 nums[mid] 和 target 的大小关系
若 nums[mid] > target，[mid, right] 区间内的元素都可以舍弃，right = mid - 1
若 nums[mid] <= target，[left, mid - 1] 区间内的元素可以舍弃，left = mid
（3）继续判断，直到 left = right
接下来，我们就来尝试编写代码，解决问题
代码实现
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ret = {-1, -1};
int len = nums.length;
// 若数组中没有元素，直接返回
if (len == 0) {
return ret;
}
int left = 0, right = len - 1;
// 查找第一个位置
while(left < right) {
int mid = (left + right) / 2;
if(target > nums[mid]) {
left = mid + 1;
} else {
right = mid;
}
}
// 判断 target 是否存在
// 不存在，直接返回
if (nums[left] != target) {
return ret;
}
ret[0] = left;
// 继续查找最后一个位置
left = 0;
right = len - 1;
while (left < right) {
int mid = (left + right + 1) / 2;
if (target < nums[mid]) {
right = mid - 1;
} else {
left = mid;
}
}
ret[1] = left;
return ret;
}
}x 的平方根
题目链接
69. x 的平方根 - 力扣（LeetCode）
题目描述
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4 输出：2
示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 231 - 1
思路分析
题目要求找到 x 的算术平方根，当其为小数时，只需要返回整数部分
我们可以通过暴力枚举来解决本题，依次枚举 0 到 x 之间的所有数 i，
若 i * i = x，直接返回 i
若 i * i > x，则返回 i - 1
class Solution {
public int mySqrt(int x) {
// 两个较大的数相乘，结果可能会超出 int 的最大范围
for(long i = 0; i <= x; i++) {
// i 的平方正好等于 x，直接返回 i
if (i * i == x) {
return (int)i;
} else if (i * i > x) {
// i 的平方大于 x，返回前一个数
return (int)(i - 1);
}
}
return -1;
}
}此时的时间复制度为 O(N)
我们还可以通过二分查找来找到 x 的算术平方根
我们需要找到某个元素，将数组划分为两个区间，然后舍去某个区间，进而在另一个区间查找
x 的平方根为 i，则 i 可以将数据划分为两个区间：
[0, i]：平方之后都是小于等于 x 的
[i + 1, x]：平方之后都是大于 x 的
将所有的数据看做是一个数组，定义 left 和 right 分别指向数组的左右两端点（也就是 0 和 x）：
此时，就可以通过 left 和 mid 找到中间位置 mid
判断 mid 的平方和 x 之间的关系：
若 mid * mid > x，则 [mid, x] 之间的数据平方和都大于 x，都可以舍弃，即 right = mid - 1
若 mid * mid <= x，则 [left, mid - 1] 之间的数据平方和都小于 x，都可以舍弃，即 left = mid
mid 不能舍弃，因为 mid 可能就是要找的平方根，还需要通过后续的判断才能决定是否舍弃
直到 left = right，循环结束，此时 left = right = mid，mid 的值就是 x 的平方根
当 [left, right] 区间内的元素个数为偶数时，此时该选择中间左边的元素还是中间右边的元素来划分区间呢？
我们还是来进行分析：
若选择左边位置来划分，此时 mid * mid = x，left = mid，区间大小不变，也就意味着会陷入死循环
而选择右边位置来划分，此时 mid * mid > x，right = mid - 1，区间减小，继续判断
因此，应该选择中间右边位置来划分区间，也就是 mid = (left + right + 1) / 2
代码实现
class Solution {
public int mySqrt(int x) {
long left = 0, right = x;
while (left < right) {
long mid = (left+ right + 1) / 2;
if ((mid * mid) > x) {
right = mid - 1;
} else {
left = mid;
}
}
return (int)left;
}
}通过上述三道题，我们对二分查找也有了基本的认识，接下来，我们就先来总结一下二分查找的使用
二分小结
首先，我们得分析清楚什么时候能够使用二分查找?
要使用二分查找，我们得找到题目中的某个规律，选取某个元素将数据划分为两部分，根据规律选择性地舍弃一部分元素，进而继续在另一部分区间内继续查找
即：
（1）分析清楚能否通过某个元素将数据划分为两部分，若可以，就可以考虑使用二分查找
（2）判断能否通过这个元素选择性地舍弃一部分元素，进而在另一部分区间内继续查找
若满足以上两点，就可以使用二分查找，接着就需要处理二分查找的细节问题
定义 left 和 right 指向区间的左右端点，当区间内元素个数为奇数时，mid 的值为中间的元素
但当区间内元素个数为偶数时，中间就会有两个元素，此时，该选择哪个元素来划分区间呢？
由于区间划分的不同，在移动 left 和 right 也会有所不同，此时，划分区间的元素也就不同：
（1）当区间划分为 [left, mid] [mid, right] 和 mid 时，若 mid 满足条件，则可以直接退出循环，而当不满足条件时，可直接舍弃左半部分 [left, mid] 区间（mid 及其左边所有元素）或是右半部分 [mid, right]（mid 及其右边所有元素），即 left = mid + 1 或 right = mid - 1，无论哪种情况，都会让区间减小，进而在更小的区间内继续查找
（2）当区间划分为 [left, mid] 和 [mid + 1, right] 时，也就是要寻找满足条件的第一个元素（也就是左端点）
可能会舍弃左半部分[left, mid]区间（mid 及其左边所有元素）left = mid + 1，或是舍弃右半部分[mid + 1, right]（mid 右边所有元素，不包括 mid）right = mid，在舍弃右半部分元素（right = mid）时，可能会出现区间不变的情况，也就可能会出现死循环，因此，需要选择中间左边元素（mid = (left + right) / 2）来划分区间，防止出现死循环，在这种情况下，找到的是满足条件的第一个元素
（3）当区间划分为 [left, mid - 1] 和 [mid, right] 时，也就是要寻找满足条件的最后一个元素（也就是右端点）
此时，可能舍弃左半部分 [left, mid - 1] 区间（mid 左边所有元素，不包括 mid）left = mid，或是舍弃右半部分 [mid, right]（mid 及其右边所有元素）right = mid - 1，在舍弃左半部分元素（left = mid）时，可能会出现区间不边的情况，也就有可能会出现死循环，因此，需要选择中间右边元素（mid = (left + right + 1) / 2）来划分区间，防止出现死循环，在这种情况下，找到的是满足条件的最后一个元素
即：
（1） mid 将区间划分为三个部分：[left, mid] [mid, right] 和 mid ，right = mid - 1，left = mid + 1，选择左边元素或右边元素都可以
（2）mid 将区间划分为两个部分：[left, mid] 和 [mid + 1, right]，查找左端点，right = mid，left = mid + 1 需要选择左边元素（mid = (left + right) / 2）来划分区间
（3）mid 将区间划分为两个部分：[left, mid - 1] 和 [mid, right]，查找右端点，right = mid - 1，left = mid ，需要选择右边元素（mid = (left + right + 1) / 2）来划分区间
总而言之，我们需要根据具体的情况来判断查找的是哪个元素，从而划分区间，根据划分区间的不同，确定 left 和 right 是如何移动的，从而确定选择哪个元素来进行划分
循环结束的条件是什么呢？
当 left = right 时循环结束，还是 left > right？
此时也需要分情况讨论：
mid 将区间划分为三个部分：[left, mid] [mid, right] 和 mid 时，当 [left, right] 区间中只有一个元素时（也就是 left = right = mid），此时，仍需要判断这个元素是否满足条件，若不满足，则会移动 left 或 right，此时 left > right，区间不再存在，说明没有满足条件的元素，此时需要退出循环，因此，循环的结束条件为 left > right
而 mid 将区间划分为两个部分时，（[left, mid] 和 [mid + 1, right] ）或是 （[left, mid - 1] 和 [mid, right]）时，当 [left, right] 区间内只有一个元素时（left = right = mid）时，区间内的最后一个元素就是要找的结果（或是没有满足条件的元素），若此时再继续判断，就会陷入死循环，因此，循环结束的条件为 left = right
求 mid 的细节
在前面，我们在确定 mid 的取值时，使用 mid = (left + right) / 2 或是 mid = (left + right + 1) / 2，但是当 left 和 right 的值都很大时，left + right 可能会溢出，因此，可以使用 mid = left + (right - left) / 2 和 mid = left + (right - left + 1) / 2 来防止溢出
最后，我们来总结一下三种划分情况的二分模板：
（1）[left, mid] [mid, right] 和 mid
while (left <= mid) {
int mid = left + (right - left) / 2; // 或是 mid = left + (right - left) / 2;
if(...) {
left = mid + 1; // 舍弃左区间
} else if(...) {
right = mid - 1; // 舍弃右区间
} else {
break; // 满足条件，该元素就是要找的元素
}
}
（2）[left, mid] 和 [mid + 1, right]，right = mid，left = mid + 1，求左端点
while (left < mid) {
int mid = left + (right - left) / 2;
if(...) {
left = mid + 1; // 舍弃左区间
} else if(...) {
right = mid; // 舍弃右区间
}
}
（3） [left, mid - 1] 和 [mid, right]，left = mid, right = mid - 1，求右端点
while (left <= mid) {
int mid = left + (right - left + 1) / 2;
if(...) {
left = mid; // 舍弃左区间
} else if(...) {
right = mid - 1; // 舍弃右区间
}
}
接下来，我们就通过更多了练习来进一步熟悉二分查找的使用
山脉数组的峰顶索引
题目链接
852. 山脉数组的峰顶索引 - 力扣（LeetCode）
题目描述
给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。
返回峰值元素的下标。
你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。
示例 1：
输入：arr = [0,1,0] 输出：1
示例 2：
输入：arr = [0,2,1,0] 输出：1
示例 3：
输入：arr = [0,10,5,2] 输出：1
提示：
3 <= arr.length <= 1050 <= arr[i] <= 106- 题目数据 保证
arr是一个山脉数组
思路分析
给定的山脉数组中的值会递增到一个峰值元素，然后递减
题目要求我们找到这个峰值元素并返回，且实现时间复杂度为 O(log(n)) 的解决方案
我们考虑能能否使用 二分查找：
（1）能否通过某个元素将数组分为两个区间？
假设峰值元素的下标为 i：
峰值元素左边的元素都小于 i，呈现上升趋势
峰值元素右边的元素都大于 i，呈现下降趋势
可以将数组划分为两个区间
（2）能否通过 arr[i] 选择性地舍弃一部分元素，进而在另一部分区间内继续查找？
mid 将数组划分为两个区间：[left, mid] 和 [mid + 1, right]
可以通过数组中元素呈现的趋势来舍弃区间：
若 mid 位置元素呈现下降趋势（mid 右边元素位于 [mid + 1, right] 区间），则舍弃 [mid + 1, right] 区间内元素，right = mid，继续在 [left, mid] 区间内查找
若 mid 位置元素呈现上升趋势（mid 及左边元素位于 [left, mid] 区间），则舍弃 [left, mid] 区间内元素，left = mid + 1，继续在 [mid + 1, right] 区间内查找
循环查找，直到 left = right = mid，，此时 left 位置的元素就是下降区间内的第一个元素
mid 将数组划分为 [left, mid] 和 [mid + 1, right] 两个区间，left = mid + 1，right = mid，需要选择中间左边元素来划分区间
接下来，我们就来尝试编写代码，解决问题
代码实现
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int len = arr.length;
int left = 0, right = len - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < arr[mid + 1]) {
// 呈上升趋势
left = mid + 1;
} else {
// 呈下降趋势
right = mid;
}
}
return left;
}
}由于本题中要查找的元素只有一个，因此也可以将数组划分为 [left, mid - 1] 和 [mid, right] 来查找上升区间内的最后一个元素
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int len = arr.length;
int left = 0, right = len - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (arr[mid] > arr[mid - 1]) {
// 呈上升趋势
left = mid;
} else {
// 呈下降趋势
right = mid - 1;
}
}
return left;
}
}寻找旋转排序数组中的最小值
题目链接
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
题目描述
已知一个长度为 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：
输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000-
nums中的所有整数 互不相同 -
nums原来是一个升序排序的数组，并进行了1至n次旋
思路分析
长度为 n 的数组，原按照升序排列，每次旋转都会将数组的第一个元素旋转到数组的最后位置，题目要求我们找到旋转之后数组的最小元素
我们通过一个具体的例子来分析题目
数组旋转前是按照升序排列的，也就是呈现上升趋势：
旋转后，就将其分成了两部分
通过上图，我们可以发现：旋转到数组最后的元素也呈现上升趋势
而后半段数据中的第一个元素，也就是我们要找的最小值
因此，我们可以将数组分为两个区间：
左边区间的元素都大于数组的最后一个元素
右边区间的元素都小于等于数组的最后一个元素
定义 left 和 right 指向区间的左右端点，通过 left 和 right 确定 mid
当 mid 落在左边区间时，[left, mid] 内的元素都大于数组的最后一个元素，都可以舍弃，left = mid + 1
当 mid 落在右边区间时，[mid, right] 内的元素都小于等于数组的最后一个元素，mid 最小，因此，可以舍弃 [mid + 1, right] 区间内的元素，right = mid
循环判断，直到循环结束
此时，left 位置元素就是被旋转到后面元素中的第一个元素
此时，left = mid + 1，right = mid，因此，mid = left + (right - left) / 2
接下来，我们就来编写代码，解决问题
代码实现
class Solution {
public int findMin(int[] nums) {
int len = nums.length;
if (len == 1) {
return nums[0];
}
int left = 0, right = len - 1;
int x = nums[right];
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= x) {
right = mid;
} else {
left = mid + 1;
}
}
return nums[left];
}
}点名
题目链接
LCR 173. 点名 - 力扣（LeetCode）
题目描述
某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。
示例 1:
输入: records = [0,1,2,3,5] 输出: 4
示例 2:
输入: records = [0, 1, 2, 3, 4, 5, 6, 8] 输出: 7
提示：
1 <= records.length <= 10000
思路分析
题目要求我们找到数组中缺失的数字
若没有同学缺失，数字中的元素是 0 - n - 1，也就意味着数组中的元素和下标是一一对应的（相同的）
但由于有一位同学缺失，那么，在这个同学缺失后，后面的元素和下标也就是不对应（不相同）的
因此，我们就可以通过这个缺失的元素 target，将数据分为两份：
target 左边的元素和下标是相同的
target 右边的元素和下标是不相同的
因此，我们可以通过二分查找，找到元素和下标不相同的第一个元素
定义 left 和 right，确定 mid 的值
若 mid = nums[mid]，则 [left, mid] 区间内所有元素都和下标相等，没有缺失的元素，舍弃，left = mid + 1
若 mid != nums[mid]，则 [mid, right] 区间内所有元素都和下标不相等，且 mid 是第一个，因此，[mid + 1, right] 区间内的所有元素都可以舍弃，right = mid
继续判断，直到循环结束
此时，left = mid + 1，right = mid，因此，mid = left + (right - left) / 2
接下来，我们就来编写代码，解决问题
代码实现
class Solution {
public int takeAttendance(int[] records) {
int len = records.length;
int left = 0, right = len - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (records[mid] == mid) {
left = mid + 1;
} else {
right = mid;
}
}
return records[left] == left ? left + 1 : left;
}
}