下面是三个模板，第一个是最容易理解的，第二三个需要背一下，基本满足所有二分题目
// 二分，查target的位置，最容易理解的
int bsearch_0(int[] nums, int l, int r)
{
while (l <= r)
{
int mid = (l + r) / 2;
if (nums[mid] == target) {
// 找到
} else if (num[mid] > target) {
r = mid - 1;
} else if (num[mid] < target) {
l = mid + 1;
}
}
}
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
// 一般用来找最左边的一个！因为当前mid如果符合条件，左边可能有或者没有，所以当前的mid不能丢掉
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
//一般用来找最右边的一个！
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
33. 搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
首先找他的分界点，选择的是找最大的那个值，比如4,5,6,7,0,1,2。要找到的是7，就是4,5,6,7中最右边的那个数。板子：
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
//一般用来找最右边的一个！
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
用nums[0]做基准。因为分界点之后的数字不可能比nums[0]大。
//找分界点
int l = 0, r = nums.size() - 1;
while(l < r){
int mid = l + r + 1 >> 1;
if(nums[mid] >= nums[0]) l = mid;
else r = mid - 1;
}
找到之后只需要判断target在哪个区间，然后进行一次普通的二分就可以了。
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.empty()) return -1;
//找分界点,最大的那个数,找最右，板子2
int l = 0, r = nums.size() - 1;
while(l < r){
int mid = l + r + 1 >> 1;
if(nums[mid] >= nums[0]) l = mid;
else r = mid - 1;
}
//判断在哪个区间
if(target >= nums[0]){
l = 0;
} else{
l = r + 1, r = nums.size() - 1;
}
//普通二分
while (l <= r){
int mid = l + r >> 1;
if(nums[mid] == target) return mid;
else if(nums[mid] > target) r = mid - 1;
else l = mid + 1;
}
return -1;
}
};
34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res;
if(nums.empty()) return {-1, -1};
//找最左，板子1
int l = 0, r = nums.size() - 1;
while(l < r){
int mid = l + r >> 1;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
if(nums[l] != target) return {-1, -1};
res.push_back(l);
//找最右，板子2
l = 0, r = nums.size() - 1;
while(l < r){
int mid = l + r + 1 >> 1;
if(nums[mid] <= target) l = mid;
else r = mid - 1;
}
res.push_back(l);
return res;
}
};
81. 搜索旋转排序数组 II
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
跟上个题类似，但是会有重复，比如2,2,2,0,2,2或者[1,3,1,1,1]。
题目板子大致跟上一个类似，就是找分界点，最大的数，用板子2。
至于怎么去除重复。。。
//去除开头和结尾的重复，压缩l
int l = 0, r = nums.size() - 1;
while(l != r && nums[l] == nums[r]){
if(nums[l] == target) return true;
else l++;
}
//记录基准点
int flag = l;
剩下的就跟I一样了
class Solution {
public:
bool search(vector<int>& nums, int target) {
if(nums.empty()) return false;
//去除开头和结尾的重复，压缩l
int l = 0, r = nums.size() - 1;
while(l != r && nums[l] == nums[r]){
if(nums[l] == target) return true;
else l++;
}
//记录基准点
int flag = l;
//找分界点,板子2
while(l < r){
int mid = l + r + 1 >> 1;
if(nums[mid] >= nums[flag]) l = mid;
else r = mid - 1;
}
if(target >= nums[flag]){
l = flag;
}else{
l = r + 1, r = nums.size() - 1;
}
while (l <= r){
int mid = l + r >> 1;
if(nums[mid] == target) return true;
else if(nums[mid] > target) r = mid - 1;
else l = mid + 1;
}
return false;
}
};
153. 寻找旋转排序数组中的最小值
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]
输出: 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
那这个就直接用板子就好了，板子2，找到最大值之后，要么他是最后一个数，要么下一个就是最小值。
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
//板子2,找最右边
while(l < r){
int mid = l + r + 1 >> 1;
if(nums[mid] >= nums[0]) l = mid;
else r = mid - 1;
}
if(r == nums.size() - 1){
return nums[0];
}else{
return nums[r + 1];
}
}
};
或者直接用板子1，找最小的数，就是找某一区间的最左边。这个时候就不能跟nums[0]比较了，要跟nums[nums.size() - 1]去比较。
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
//板子1，找最左边的值
while(l < r){
int mid = l + r >> 1;
if(nums[mid] <= nums[nums.size() - 1]) r = mid;
else l = mid + 1;
}
return nums[l];
}
};
154. 寻找旋转排序数组中的最小值 II
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
注意数组中可能存在重复的元素。
示例 1：
输入: [1,3,5]
输出: 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
熟悉套路之后这就不是一道难题了，要么做的出来，要么GG，既然有重复，那么就按之前的方式，把l压缩，再用板子1，找最小的元素（该区间中最左边的元素）。
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while(l < r){
int mid = l + r >> 1;
if(nums[mid] <= nums[nums.size() - 1]) r = mid;
else l = mid + 1;
}
return nums[l];
}
};
162. 寻找峰值
峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。
示例 1:
输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-peak-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
找下规律就行了，看当前的mid和左右两边的关系，如果是峰值，就直接返回，不然就再迭代一下。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
if(nums.size() == 1){
return 0;
} else if(nums.size() == 2){
if(nums[0] < nums[1])
return 1;
else
return 0;
}
nums.insert(nums.begin(), INT_MIN);
nums.push_back(INT_MIN);
int res = -1;
int left = 0, right = nums.size() - 1;
while (left < right){
int mid = left + right + 1 >> 1;
int mid_num = nums[mid];
int mid_left_num = nums[mid - 1];
int mid_right_num = nums[mid + 1];
if(mid_num > mid_left_num && mid_num > mid_right_num){
res = mid;
break;
} else if(mid_num > mid_left_num && mid_num < mid_right_num){
left = mid;
} else{
right = mid;
}
}
return res - 1;
}
};
274. H 指数
给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。
h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数 不超过 h 次。）
例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇
示例：
输入：citations = [3,0,6,1,5]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/h-index
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题要关注的是i和citations[i]的关系，除去题目给的例子，再比如[5,4,1,0]的答案是2，所以答案不一定在数组中。我们必须要把数组按降序排序，然后搜索h，用二分法，找最右边的那个满足citations[mid] >= (mid + 1)的位置。
class Solution {
public:
int hIndex(vector<int>& citations) {
if(citations.empty()) return 0;
sort(citations.begin(), citations.end());
reverse(citations.begin(), citations.end());
int l = 0, r = citations.size() - 1;
//板子2
while(l < r){
int mid = l + r + 1 >> 1;
if(citations[mid] >= (mid + 1)) l = mid;
else r = mid - 1;
}
//判断一下是否合格
if((r + 1) <= citations[r]) return r + 1;
return 0;
}
};
275. H 指数 II
给定一位研究者论文被引用次数的数组（被引用次数是非负整数），数组已经按照 升序排列 。编写一个方法，计算出研究者的 h 指数。
h 指数的定义: “h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数不多于 h 次。）"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/h-index-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题已经升序排列，所以刚好更上面相反，所以我们倒过来用板子1，找最左边的那一个。
class Solution {
public:
int hIndex(vector<int>& citations) {
if(citations.empty()) return 0;
int l = 0, r = citations.size() - 1;
//板子1
while(l < r){
int mid = l + r >> 1;
if(citations[mid] >= (citations.size() - mid)) r = mid;
else l = mid + 1;
}
if((citations.size() - r) <= citations[r]) return citations.size() - r;
return 0;
}
};
278. 第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/first-bad-version
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题比较简单但是有一个小坑，测试用例会有超过max_int的数据，l + r >> 1的方式会不给过，就要换成l + (r - l) / 2。
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int l = 1, r = n;
//板子1
while(l < r){
int mid = l + (r - l) / 2;
if(isBadVersion(mid)) r = mid;
else l = mid + 1;
}
return l;
}
};
分巧克力（蓝桥杯）
问题描述
儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：
1. 形状是正方形，边长是整数
2. 大小相同
当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？
输入格式
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
样例输入
2 10
6 5
5 6
样例输出
2
起码能分出k块，比如[1,2,3,4,5,6,7]其中，[1,2,3]能分出k块，所以答案是3。就是找满足条件的最大值，即最右边的数，模板2。
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
int main(){
int n, k;
cin >> n >> k;
vector<pair<int, int> > nums;
for(int i = 0; i < n; i++){
int hi, wi;
cin >> hi >> wi;
nums.push_back(make_pair(hi, wi));
}
int l = 1, r = 100000;
while(l < r){
int mid = l + r + 1 >> 1;
int tmp = 0;
for(int i = 0; i < n; i++){
tmp += (nums[i].first / mid) * (nums[i].second / mid);
}
if(tmp >= k){
l = mid;
}else{
r = mid - 1;
}
}
cout << l;
}
远亲不如近邻
牛牛最近搬到了一座新的城镇，这个城镇可以看成是一个一维的坐标系。城镇上有n个居民，第i个居民的位置为ai。现在牛牛有m个搬家方案，在第i个方案中他会搬到位置xi。
俗话说的好，远亲不如近邻。现在牛牛想知道，对于每个搬家方案，搬家后与最近的居民的距离为多少。
输入
3,2,[2,4,7],[5,8]
返回值
[1,1]
说明
第一个方案搬到位置5，与5最近的居民在位置4，距离为1.
第二个方案搬到位置8，与8最近的居民在位置7，距离为1
- 两边的：每个方案先跟两边的比较，这样就不用进入二分。
- 中间的：二分找第一个比他大的位置l，l-1就是第一个比他小的，比较与这两个位置的距离
class Solution {
public:
/**
* 远亲不如近邻
* @param n int整型 居民个数
* @param m int整型 方案个数
* @param a int整型vector 居民的位置
* @param x int整型vector 方案对应的位置
* @return int整型vector
*/
vector<int> solve(int n, int m, vector<int>& a, vector<int>& x) {
// write code here
vector<int> res;
if(a.empty() || x.empty()){
return res;
}
sort(a.begin(), a.end());
int len = x.size();
for(int i = 0; i < len; i++){
if(x[i] < a[0]){
res.push_back(a[0] - x[i]);
}else if(x[i] > a[a.size() - 1]){
res.push_back(x[i] - a[a.size() - 1]);
}else{
//找第一个比他大的
int l = 0, r = a.size() - 1;
while(l < r){
int mid = l + r >> 1;
if(a[mid] > x[i]) r = mid;
else l = mid + 1;
}
res.push_back(min(a[r] - x[i], x[i] - a[r - 1]));
}
}
return res;
}
};
