这是五月集训的第9日，今日的训练内容是 二分查找
二分查找的概述二分查找顾名思义，就是使用二分法的方式来寻找一个 有序 数组中的某一个 target 的方法。这样就成功的把时间复杂度从 n 降低到了 logn 。它的写法可以参考如下：
给一个有序数组和一个值target，查找有无这个值，如果没有就返回 -1。
int search(int* nums, int numsSize, int target){
int l=0,r=numsSize-1; //(1)
while(l<=r){ //(2)
int mid = (l+r)/2; //(3)
if(nums[mid]>target){ //(4)
r = mid - 1;
}
if(nums[mid] //(5)
l = mid + 1;
}
if(nums[mid]==target){ //(6)
return mid;
}
}
return -1; //(7)
}
以这题举例来大致对二分查找进行概述：
1.首先定义一下区间的左端点和右端点，并且初始化值为 0 和 numsSize-1 。
2.最多循环到两边的端点相重合，说明整个数组已经被遍历完全了。
3.定义一个区间中点（这个中点指的是左端点到右端点的那个区间）
4.如果区间中点的值是大于目标值的，那么说明目标值在区间的左边，那么可以缩小区间的范围了，将右端点移动到刚刚区间中点的左边开始遍历。
5.类似上面。
6.如果区间中点就等于目标值，那说明找到要的值了，直接返回区间中点下标就可以了。
7.如果遍历完了数组都不存在的话，说明没有这个值，返回 -1。
https://leetcode.cn/problems/search-insert-position/
题目概述解题思路给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
所给的数组是一个有序的数组，因此这个题目是一个二分查找的题目。在仔细读题并且梳理过后可以得出，本题其实需要找的就是大于等于 target 的最小下标，因为最后需要顺序插入的数字肯定是小于后一个数的，并且插入后其实占用的就是其后一个数在插入前的位置，因此只要找到大于等于 target 的最小下标即可。然后使用二分法不断缩小范围即可。
源码剖析int searchInsert(int* nums, int numsSize, int target){
int l=0,r=numsSize-1;
int ans=numsSize;
while(l<=r){
int mid = (l+r)/2;
if(nums[mid]>target){
ans = mid;
r = mid-1;
}
if(nums[mid]
定义了一个用于存储满足题目要求数据的变量 ans ans时刻都是大于 target 的最小下标。
2.力扣704
原题链接
https://leetcode.cn/problems/binary-search/
题目概述
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
解题思路
这题就是前面介绍二分查找使用的例题，详见介绍。
源码剖析
int search(int* nums, int numsSize, int target){
int l=0,r=numsSize-1; //(1)
while(l<=r){ //(2)
int mid = (l+r)/2; //(3)
if(nums[mid]>target){ //(4)
r = mid - 1;
}
if(nums[mid] //(5)
l = mid + 1;
}
if(nums[mid]==target){ //(6)
return mid;
}
}
return -1; //(7)
}
3.力扣剑指offer 53
原题链接
https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
题目概述
统计一个数字在排序数组中出现的次数。
解题思路
首先还是对原来的数组进行二分查找，如果没有找到这个数的话则说明原来的数组中本来就没有这个数，那么直接返回0就可以了。如果找到了这个数，因为这个数组是有序的数组，所以相同的数字的位置肯定是相邻的，那么也就只需要把之前找到的下标分别向前向后遍历一下，一旦发现了不相等的数字直接 break; 就可以了，每找到一个数就给计数器加一（找到数字的当时就要使得计数器加一），最后返回累加的值就可以了。
源码剖析
int search(int* nums, int numsSize, int target){
if(numsSize==0) return 0;
int mid1 = 0;
int ans = 0;
int l = 0, r = numsSize-1;
while(l<=r){
int mid = (l+r)/2;
if(nums[mid]>target) r = mid-1;
if(nums[mid]
ans++;
mid1 = mid;
break;
}
}
if(nums[mid1]==target){
int x = mid1;
for(x=mid1-1;x>=0;--x){
if(nums[x]==target) ans++;
else break;
}
for(x=mid1+1;x
if(nums[x]==target) ans++;
else break;
}
}
return ans;
}
值得注意的是，当数组的容量为0时，直接使用判断语句处理会比较方便，不需要考虑下标等各种问题。
4.力扣911
原题链接
https://leetcode.cn/problems/online-election/
题目概述
给你两个整数数组 persons 和 times 。在选举中，第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的。
对于发生在时刻 t 的每个查询，需要找出在 t 时刻在选举中领先的候选人的编号。
在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。
实现 TopVotedCandidate 类：
TopVotedCandidate(int[] persons, int[] times) 使用 persons 和 times 数组初始化对象。
int q(int t) 根据前面描述的规则，返回在时刻 t 在选举中领先的候选人的编号。
解题思路
暂时做记录，等学习 c++ 后回来重新思考。
