class Solution {
public:
int binarySearch(vector<int>& nums, int target, bool lower) {
int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > target || (lower && nums[mid] >= target)) {
right = mid - 1;
ans = mid;
} else {
left = mid + 1;
}
}
return ans;
}
vector<int> searchRange(vector<int>& nums, int target) {
int leftIdx = binarySearch(nums, target, true);
int rightIdx = binarySearch(nums, target, false) - 1;
if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {
return vector<int>{leftIdx, rightIdx};
}
return vector<int>{-1, -1};
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-3-4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
34.给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
上诉是LeetCode给的标准答案
标准答案思路：首先是有序序列找数，首先想到二分查找，但是二分前后的边界位置有需要对二分有深入了解，
1其实关键就是if (nums[mid] > target || (lower && nums[mid] >= target))这个判断取不取等号的问题，
2当不取等号的时候位置会向右偏移（只要小于等于left就向右移）由此取到右边界，同理当取了等号就会向左移动（只有小于left向右移动，当等于right就向左）由此取到左边界
3while (left <= right) 这里取小等于是因为若只取小于，在数组只有一个元素时候进入不了判断
4bool 主要是为了代码重用。就是找左右边界的代码重用，其实就是取等号，不取等号的代码重用。
这下面是我根据标准答案改的
class Solution {
public:
int binarySearch(vector<int>&nums ,int target,bool lower){
int right=nums.size()-1,left=0;
int mid=(right+left)/2;
while(left<=right){
if(nums[mid]>target||lower&&nums[mid]>=target)
{right=mid-1;}
else
left=mid+1;
mid=(right+left)/2;
}
return left;
}
vector<int> searchRange(vector<int>&nums, int target) {
int left=binarySearch(nums,target,true);
int right=binarySearch(nums,target,false)-1;
if(left<=right&&nums[left]==target)
return vector<int>{left,right};
else return vector<int>{-1,-1};
}
};
其实就是答案中多了一个ans，我觉得没啥用。。。就取消了。。。最后在 int right=binarySearch(nums,target,false)-1;这一步-1就可以了
704
最基础算法二分搜索
class Solution {
public:
int search(vector<int>& nums, int target) {
int right=nums.size()-1,left=0,mid=left + ((right - left) / 2);
while(left<=right){
if(nums[mid]>target)
right=mid-1;
else if(nums[mid]<target) left=mid+1;
else return mid;
mid=left + ((right - left)/2);
}
return -1;
}
};
关于这个算法：虽然思路简单，但其中还是有些模糊的点，LeetCode评论中给出了较为不错的回答，
二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？
大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是**循环不变量**规则。
写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。
下面我用这两种区间的定义分别讲解两种不同的二分写法。
### 二分法第一种写法
第一种写法，我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。
区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：
- while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
- if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle
如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同。
-
有如下两点：
- while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
- if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]
35 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
leetcode 的一道题，依旧是二分，这道题因为要有插入位置，所以判断稍微复杂了一些
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left=0,right=nums.size(),mid=(left+mid)/2;
int size=right;
while(left<right){
if(nums[mid]>target)
right=mid-1;
else if(nums[mid]<target)
left=mid+1;
else
return mid;
mid=(left+right)/2;
}
cout<<left<<right<<mid;
if(left>=size)
return left;
else
if(nums[left]>=target)
return left;
else return left+1;
}
};
为什么是left<rihght因为若left<=right时找target会导致数组会越界。
OK 写到这里可以对二分法的细节处理做一些总结了。。。
1：计算 mid 时需要防止溢出，代码中left + (right - left) / 2就和(left + right) / 2的结果相同，但是有效防止了left和right太大直接相加导致溢出。
2：二分查找时关于while终止条件的等号取舍。
while(left <= right)的终止条件是left == right + 1，写成区间的形式就是[right + 1, right]，或者带个具体的数字进去[3, 2]，可见这时候区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的，直接返回 -1 即可。
while(left < right)的终止条件是left == right，写成区间的形式就是[left, right]，或者带个具体的数字进去[2, 2]，这时候区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间[2, 2]被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就是错误的。
说到底是否取等号是和你的搜索区间之间相关的。
第二个，寻找左侧边界的二分查找：
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid
因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧右侧边界以锁定左侧边界
第三个，寻找右侧边界的二分查找：
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid
因为我们需找到 target 的最右侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界
又因为收紧左侧边界时必须 left = mid + 1
所以最后无论返回 left 还是 right，必须减一
对于寻找左右边界的二分搜索，常见的手法是使用左闭右开的「搜索区间」，我们还根据逻辑将「搜索区间」全都统一成了两端都闭，便于记忆，只要修改两处即可变化出三种写法：
int binary_search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if(nums[mid] == target) {
// 直接返回
return mid;
}
}
// 直接返回
return -1;
}
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回，锁定左侧边界
right = mid - 1;
}
}
// 最后要检查 left 越界的情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回，锁定右侧边界
left = mid + 1;
}
}
// 最后要检查 right 越界的情况
if (right < 0 || nums[right] != target)
return -1;
return right;
}
二分法的所有细节大体便如上所说。
下面是二分的更加难的习题
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
示例 1：
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
来源：力扣（LeetCode）
这道题首先用了动态规划的思想，然后为了减少时间用了一下二分
