《五月集训》（第九天）——二分查找

前言：

五月集训，前面为学习内容，想要一起学习的可以看一看，最后的才是五月集训每天的作业。

一、知识点

二分查找普通用法就是在一个有序数组中，一头一尾不断向中间逼近目标值，已达到降低复杂度的目的。

二、课堂习题

这里的题均出自《算法零基础100讲》
着急学习的同学去看专栏吧！！！

三、作业

35. 搜索插入位置
704. 二分查找
剑指 Offer 53 - I. 在排序数组中查找数字 I
911. 在线选举
解题思路：
1.模板题，定义一个变量存储结果，不断二分查找即可；
2.同上，多一步判断找到的元素是否与目标值相等；
3.找到目标值的位置，然后再找到比目标值大一个的位置，两个值相减即是目标值的数量；
4.这题看的大佬们的题解思路（等有空会自己补的ORZ），简单来说就是将每个时间的胜利者统计出来，然后二分查找对应的时刻。
代码：

class Solution {    public int searchInsert(int[] nums, int target) { int l = 0,r = nums.length-1; int ans = nums.length; while(l <= r){     int mid = (l+r)>>1;     if(nums[mid] >= target){  ans = mid;  r = mid - 1;     }else{  l = mid + 1;     } } return ans;    }}

class Solution {    public int search(int[] nums, int target) { int n = nums.length; int l = 0,r = n - 1; int ans = n; while(l <= r){     int mid = (l+r) >> 1;     if(nums[mid] >= target){  ans = mid;  r = mid - 1;     }else{  l = mid + 1;     } } if(ans == n){     return -1; }else if(nums[ans] != target){     return -1; } return ans;    }}

class Solution {    public int search(int[] nums, int target) { int n = nums.length; int index = bSearch(nums,n,target); if(index == n || nums[index] != target){     return 0; } return bSearch(nums,n,target+1) - index;    }    public int bSearch(int[] nums,int n,int target){ int l = 0,r = n - 1; int ans = n; while(l <= r){     int mid = (l+r)>>1;     if(nums[mid] >= target){  ans = mid;  r = mid - 1;     }else{  l = mid + 1;     } } return ans;    }}

class TopVotedCandidate {    List<int[]> list = new ArrayList<>();    public TopVotedCandidate(int[] persons, int[] times) { int val = 0; Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < times.length; i++) {     map.put(persons[i], map.getOrDefault(persons[i], 0) + 1);     if (map.get(persons[i]) >= val) {  val = map.get(persons[i]);  list.add(new int[]{times[i], persons[i]});     } }    }    public int q(int t) { int l = 0, r = list.size() - 1; while (l < r) {     int mid = l + r + 1 >> 1;     if (list.get(mid)[0] <= t){  l = mid;     }else{  r = mid - 1;     }  } return list.get(r)[0] <= t ? list.get(r)[1] : 0;    }}/** * Your TopVotedCandidate object will be instantiated and called as such: * TopVotedCandidate obj = new TopVotedCandidate(persons, times); * int param_1 = obj.q(t); */

四、总结

对于算法的掌握还是不够熟练，需要进行反复训练！
另外，剩下的课堂训练题目留到下个月的集训啦(●ˇ∀ˇ●)