目录
二分查找
在排序数组中查找元素的第一个和最后一个位置
搜索插入位置
一个数组经过划分后具有二段性的都可以用二分查找
二分查找
704. 二分查找 - 力扣（LeetCode）
暴力解法：直接遍历数组，找到 target 便返回下标，数组都遍历完了仍找不到，则返回 -1，时间复杂度为 O ( n )（最坏的情况：如果数组中不存在 target，则需要遍历整个数组）。
注意到题目中提供的数组是升序的，即数组从左往右是递增的。我们在数组中随意找个下标，设为 i，
1、如果nums[ i ] > target ，由于数组升序，说明 i 右边的数（即比 nums[ i ] 大的数）一定也大于 target，所以 target 应该落在 i 的左边，我们就不必遍历 i 右边的数了
2、同理，如果nums[ i ] < target ，由于数组升序，说明 i 左边的数（即比 nums[ i ] 小的数）一定也小于 target，所以 target 应该落在 i 的右边，我们就不必遍历 i 左边的数了
3、如果 nums[ i ] == target，那么 i 就是我们想要的返回值
于是衍生出二分查找， 定义 left、right、mid，
1、如果 nums[ mid ] > target，mid 左边的数不必遍历了，所以 right = mid - 1
2、如果 nums[ mid ] < target，mid 右边的数不必遍历了，所以 left = mid + 1
3、如果 nums[ mid ] == target，说明找到了，返回 mid
4、如果 left > right，说明数组中不存在 target ，返回 -1
要注意 mid 的计算，防止溢出！！
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0;
int right=nums.size()-1;
while(left<=right)
{
//int mid=(left+right)/2;
int mid=left+(right-left)/2;//防止 left+right 溢出
if(nums[mid]>target) right=mid-1;
else if(nums[mid]<target) left=mid+1;
else { return mid;}
}
return -1;
}
};在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
暴力解法：把数组从头到尾遍历一遍，并标记 target 第一次和最后一次出现的下标，时间复杂度为 O（n）。
注意到，题目提供的数组为非递减数组，即 nums[ i ] <= nums[ i+1 ]。
在分析问题之前，我们先区分下面两个 mid 的计算：
int mid=left+(right-left)/2;
int mid=left+(right-left+1)/2;1、如果 nums[ left ] ~ nums[ right ] 中有奇数个数，mid 的两种计算方法没有区别，都会指向同一个下标；
2、如果 nums[ left ] ~ nums[ right ] 中有偶数个数，mid = left + ( right - left )/2 相当于向下取整，mid = left + ( right - left +1 )/2 相当于向上取整。
比如下图，left = 0，right = 5，left + ( right - left )/2 = 2.5，但由于 mid 为 整型，最终 mid 为 2（相当于向下取整）；mid = left + ( right - left +1 )/2 = 3（相当于对 2.5 向上取整）。
我们先找 target 第一次出现的下标 begin ：begin 下标相当于把数组分为两段，下标 0 ~ begin -1 的数小于 target ，下标为 begin ~ nums.size( ) -1 的数大于等于 target 。
再找出 target 最后一次出现的下标 end ：end 下标也把数组分为两段，下标 0 ~ end 的数小于等于 target，下标为 end+1 ~ nums.size( ) -1 的数大于 target。
我们可以根据上面的二段性来找 target 第一个和最后一个位置。
先找 begin，left 从 0 开始，right 从 nums.size( ) -1 开始，
1、如果 nums[ mid ] < target，说明下标小于等于 mid 的数一定小于 target，所以 left = mid + 1；
2、如果 nums[ mid ] >= target，说明下标大于 mid 的数一定大于 target，但是下标等于 mid 的数可能大于 target，也可能等于 target，所以 right = mid，如果 right = mid -1 ，那么 nums[ mid ] == target 的情况会被跳过，即可能是第一次出现的下标被跳过了；
3、在找 begin 时，mid = left + ( right - left )/2，因为 mid 向下取整才可以找出在一连串连续出现的 target 中找出第一次出现的下标（相当于整体都靠左边找）
4、left = right 时，while 循环结束，停止寻找，我们需要判断 while 循环结束时 nums[ left ] == target，因为数组中可能不存在 target，如果不存在，可以直接返回 -1 了，没有必要找最后一次出现的下标
在找 end 位置时，也是相似的道理，
1、如果 nums[ mid ] <= target，说明下标小于等于 mid 的数一定小于等于 target，同样，考虑到下标为 mid 的数可能等于 target，所以 left = mid；
2、如果 nums[ mid ] > target，说明下标大于等于 mid 的数一定大于 target，所以 right = mid -1；
3、在找 end 时，mid = left + ( right - left +1 )/2，因为 mid 向上取整才可以找出在一连串连续出现的 target 中找出最后一次出现的下标（相当于整体都靠右边找）
TIP：如果 right 的计算中出现了 -1，那么 mid 的计算中就会出现 +1
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size()==0) return {-1,-1};
int left=0;
int right=nums.size()-1;
//找左端点
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]<target) left=mid+1;
else right=mid;
}
int begin=0;
if(nums[left]!=target) return {-1,-1};
else begin=left;
//找右端点
left=0;
right=nums.size()-1;
while(left<right)
{
int mid=left+(right-left+1)/2;
if(nums[mid]>target) right=mid-1;
else left=mid;
}
return {begin,right};
}
};搜索插入位置
35. 搜索插入位置 - 力扣（LeetCode）https://leetcode.cn/problems/search-insert-position/description/
同样可以把数组根据 target 分为两段，一边小于 target，一边大于等于 target。
1、如果 nums[ mid ] < target，则 left = mid +1 ；
2、如果 nums[ mid ] >= target，则 right = mid；
3、当 left = right 时，退出 while 循环，
a.如果 nums[ left ] < target，说明数组中不存在 target，我们需要把 target 插入到下标为 left +1 的位置中，返回 left +1 ;
b.如果 nums[ left ] > target，同样说明数组中不存在 target，需要把 target 插入到下标为 left 位置中，返回 left;
c.如果 nums[ left ] == target ,说明数组中存在 target，不需要插入，直接返回 left
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left=0,right=nums.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]<target) left=mid+1;
else right=mid;
}
if(nums[left]<target) return left+1;//target比nums[left]大，则在left+1位置插入
else return left;//target比nums[left]小，则在left位置插入，若相等，则返回在数组中的下标
}
};
