二分查找
二分查找
例题:返回长度为
N
、按升序排列的整数数组nums
中第一个大于等于target
的数的位置,如果所有数都小于等于target
,返回数组长度。注意算法时间复杂度必须为$O(\log N)$
考虑二分查找(红蓝染色法),指定$L,R$分别为询问的左右边界,考虑开区间的情况即$(L,R)$,$M=\lfloor (L+R)/2\rfloor$为当前正在询问的数字。
如果nums[M] < target
,则表明M
左边的数组都小于target
,需要查询M
右边的数字,更新L=M
,即将边界更新为(M, R)
,否则表明nums[M]
右侧的数都大于等于target
,第一个大于等于target
的数一定为M
或在M
左侧,更新R=M
,即将边界更新为(L,M)
,终止条件为L + 1 >= R
,此时R
指向的数就一定为第一个给大于等于target
的数。
在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)
给你一个按照非递减顺序排列的整数数组
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]提示:
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums
是一个非递减数组-10^9 <= target <= 10^9
注意到题目中提到数组元素按非递减顺序排序,则可以采用二分查找法。
首先实现方法int lowerBound(int[] nums, int target)
:给定一个按照非递减顺序排列的整数数组 nums
,和一个目标值 target
,找出第一个大于等于target
的数的位置。那么可以将其他问题使用该方法解决:
- 找出第一个大于
target
的数的位置:lowerBound(nums, target+1)
找出最后一个小于
target
的数位置:lowerBound(nums, target)-1
找出最后一个小于等于
target
的数位置:lowerBound(nums, target+1)-1
这里使用两侧开区间的循环不变式,即(left, right)
,循环不变式中所有在left
以及left
左边的数都必定严格小于target
,所有在right
以及right
右边的数都必定大于等于target
,则代码可写为:
1 | class Solution { |
礼盒的最大甜蜜度
给你一个正整数数组
price
,其中price[i]
表示第i
类糖果的价格,另给你一个正整数k
。商店组合
k
类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。返回礼盒的 最大 甜蜜度。
示例 1:
1
2
3
4
5 输入:price = [13,5,1,8,21,2], k = 3
输出:8
解释:选出价格分别为 [13,5,21] 的三类糖果。
礼盒的甜蜜度为 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8 。
可以证明能够取得的最大甜蜜度就是 8 。示例 2:
1
2
3
4
5 输入:price = [1,3,1], k = 2
输出:2
解释:选出价格分别为 [1,3] 的两类糖果。
礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2 。
可以证明能够取得的最大甜蜜度就是 2 。示例 3:
1
2
3 输入:price = [7,7,7,7], k = 2
输出:0
解释:从现有的糖果中任选两类糖果,甜蜜度都会是 0 。
此处可以得知可能的甜蜜度的下限为0,上限为最大价格减去最小价格。所以先对price
升序排序,确定好甜蜜度的上下限再进行二分查找。查找时的判断条件为判断当前甜蜜度能否满足至少有k
类糖果符合甜蜜度的要求。
对于条件判断,可以考虑相邻元素之间的差值,以price[0]
初始化参考价格prev
,向后遍历,如果price[i] - prev < mid
,则继续向后遍历;如果price[i] - prev >= mid
,则表明price[i]
符合当前甜蜜度的要求,添加到选择的糖果类别中并将prev
更新为price[i]
。
1 | class Solution { |