力扣刷题 二分查找学习计划 第三天
367. 有效的完全平方数
简单二分查找，需要注意的是溢出问题
class Solution {
public:bool isPerfectSquare(int num) {int p=1,q=num/2;if(num==1){return 1;}while(p<=q){long long int mid=(q+p)/2;if(mid*mid==num){return 1;}else if(mid*mid>num){q=mid-1;}else{p=mid+1;}}return 0;}
};
1385. 两个数组间的距离值
一眼没看出来用二分怎么写，看了下数据量给得小，于是用暴力试试，过了。
class Solution {
public:int findTheDistanceValue(vector& arr1, vector& arr2, int d) {int ans=0;for(int i=0;i 看了下答案才知道怎样用二分，不过答案描述的并不清晰。
答案的意思是：假设arr1中当前元素为x，那么要在arr2中寻找两个最接近x的数y1，y2，且y1
另外，还在答案中发现了个没见过的函数 lower_bound( )，于是去了解了一下。
在从小到大排序的数组内有：
lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到就返回该数字的地址，未找到则返回end。通过返回的地址减去起始地址begin,可得到找到数字在数组中的下标。
upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
在从大到小排列的数组则相反。
最后放上代码
class Solution {
public:int findTheDistanceValue(vector& arr1, vector& arr2, int d) {int ans=0;sort(arr2.begin(),arr2.end());for(int i=0;i=0){if(arr2[p]-arr1[i]>d&&arr1[i]-arr2[p-1]>d){n=1;}}else if(p==arr2.size()){if(arr1[i]-arr2[arr2.size()-1]>d){n=1;}}else if(p==0){if(arr2[0]-arr1[i]>d){n=1;}}if(n){ans++;}}return ans;}
}; 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！