\bigcap \bigcup \oint \frac{a}{b}
思路
33. 搜索旋转排序数组
数组分为递增的两个部分,前半部分都大于等于nums[0], 后半部分都小于nums[0], 我们先二分出分界点,然后根据target和nums[0]的大小关系,在对应的部分二分出target所在的位置。
278. 第一个错误的版本
给定函数isBadVersion(i),如果第i个版本是有bug的,则返回true,否则返回false。所以版本1到n的前半部分是没有bug的,后半部分是有bug的,只要二分出有bug的第一个版本即可。
275. H 指数 II
给定论文的被引次数,按照升序排列,我们要二分出其h指数,h指数是指这些论文中有h篇论文至少被引用了h次的最大的那个h。之所以说是最大的h,因为如果有h篇论文被引用h次,那么也肯定有任意a<=h满足至少a篇论文被引用a次,所以不妨假设我们要找到的答案是x,所以从0~x是一定满足该条件的,x+1~n则不满足。所以我们只需要二分出x即可。
162. 寻找峰值
与其说这道题是一道二分的题目,我觉得这道题更像是一个双指针的题目:
给定一个区间[l, r],设mid = (l + r) / 2;
如果说nums[mid] > nums[mid + 1] 就说明峰值一定在l~mid之间;
反之若nums[mid] < nums[mid + 1] 则说明峰值一定在mid + 1 ~ r之间;
所以我们每次都选择一定有峰值的那半部分,直到区间缩小到峰值的那一点。
287. 寻找重复数
= = 表达能力有限,找到一个思路相同的题解,见: 287. 寻找重复的数
代码
33. 搜索旋转排序数组
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size();
// 二分到最小值
while(l < r){
int mid = (l + r) / 2;
if(nums[mid] < nums[0]) r = mid;
else l = mid + 1;
}
// 从前半区间找到target
if(target >= nums[0]) l = 0, r -- ;
// 从后半区间找到target
else r = nums.size() - 1;
while(l < r){
int mid = (l + r) / 2;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
// 如果找到了target,返回下标
if(nums[r] == target) return r;
// 没找到
return -1;
}
};
278. 第一个错误的版本
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
// 对版本进行二分查找
int l = 1, r = n;
while(l < r){
// 0LL 防止int溢出
int mid = (0LL + l + r) / 2;
// 二分出最早出现bug的版本
if(isBadVersion(mid)) r = mid;
else l = mid + 1;
}
return l;
}
};
275. H 指数 II
class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size();
int l = 0, r = n;
while(l < r){
// 二分出h指数
int mid = (l + r + 1) / 2;
// citations[n - mid]是引用数第mid多的论文的引用数
// citations[n - mid] >= mid,成立则表示有mid篇论文的引用数至少为mid
if(citations[n - mid] >= mid) l = mid;
else r = mid - 1;
}
return l;
}
};
162. 寻找峰值
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while(l < r){
int mid = (l + r) / 2;
// 如果mid点高于mid+1,则说明峰值在nums[l, mid]中。
if(nums[mid] > nums[mid + 1]) r = mid;
// 反之,峰值则在nums[mid + 1, r]中。
else l = mid + 1;
}
return l;
}
};
287. 寻找重复数
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int l = 1, r = nums.size() - 1;
while(l < r){
int mid = (l + r) / 2;
// 记录大小在[l, mid]中的数的个数。
int lcnt = 0;
for(auto t : nums)
if(l <= t && t <= mid) lcnt ++ ;
if(lcnt > mid - l + 1) r = mid;
else l = mid + 1;
}
return l;
}
};