目录
什么是二分查找
二分查找是一种高效的搜索算法,适用于在一组数据中中查找某个特定元素,其基本思路是通过不断将查找范围减半来快速定位目标元素
接下来,我们就通过具体的问题,来学习二分查找
二分查找
题目链接
题目描述
给定一个 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 的平方根
题目链接
题目描述
给你一个非负整数 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; // 舍弃右区间
}
}
接下来,我们就通过更多了练习来进一步熟悉二分查找的使用
山脉数组的峰顶索引
题目链接
题目描述
给定一个长度为 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 <= 105
0 <= 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.length
1 <= 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];
}
}
点名
题目链接
题目描述
某班级 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;
}
}