@myecho
2019-03-26T21:47:39.000000Z
字数 5074
阅读 785
二分搜索问题
二分&三分
推荐使用middle = left + (right - left) / 2;
而不是middle = (left + right) / 2;防止溢出
- STL中函数的使用
如binary_search(exams.begin(), exams.end(), a),lower_bound,以及upper_bound等函数的使用
lower_bound返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置
upper_bound也就是“元素值>查找值”的第一个元素的位置，找不到时也返回last - 自己实现的各种二分函数
/*在一个数组里面查找最后一次出现的值v*/int binarySearchLast(int *a, int l, int h, int v){if(!a || l > h)return -1;int mid;while (l+1 < h) //这里应当是一个左闭右闭区间{mid = (l+h)/2;if(a[mid] < v)l = mid + 1;else if(a[mid] == v)l = mid;elseh = mid - 1;}if(a[l+1] == v)return l+1;else if(a[l] == v)return l;else return -1;}
考虑下边几种边界情况
/*在一个数组里面查找第一次出现的值v*/int binarySearchFirst(int *a, int l, int h, int v){if(!a || l > h)return -1;int mid;while (l < h){mid = (l+h)/2;if (a[mid] < v)l = mid + 1;else if(a[mid] == v)h = mid;else h = mid - 1;}if(a[l] == v) //这里不能像下边一样处理 比如l=h 且a[l]=v的情况会陷入死循环return l;return -1;}
寻找一个值为v的元素int binarySearch(int *a, int l, int h, int v){if (!a || l > h)return -1;int mid;while(l < h){mid = (l+h)/2;if(a[mid] == v)return mid;else if(a[mid] < v)l = mid + 1;else h = mid - 1;}if(a[l] == v) // l==h时加的判断或者直接在上边改为while(l <= h)return l;return -1;}
再有比如寻找插入位置题目leetcode 35，需要处理一类特殊情况当把high=nums.size()-1时，如何返回
Input: [1,3,5,6], 7
Output: 4
if (low == nums.size() - 1 && target > nums[nums.size() - 1]) return nums.size();
- 利用二分解决搜索问题
URAL Monthly Expense
思路实现：对要求的值进行二分搜索，（因为其为有序队列，ans越大，分组数越少），以分组数作为判别条件，同时要考虑到寻找能时组数成立之中的最小值。
#include<iostream>#include<vector>#include<queue>using namespace std;int a[100005];int n,m;int judge_group(int mid){int sum=0;int group=1;for(int i=0;i<n;++i){if(sum+a[i]<=mid){sum+=a[i];}else{sum=a[i];group++;}}return group;}int main(){ios::sync_with_stdio(false);//必须放置在首行cin>>n>>m;int left=0; //分为n组int right=0; //全部分为一组for(int i=0;i<n;++i){cin>>a[i];right+=a[i];if(a[i]>left){left=a[i];}}int mid;while(left<right){mid=(left+right)/2;int cnt=judge_group(mid);if(cnt>m){left=mid+1;}else if(cnt<m){right=mid-1;}else right=mid;}cout<<left<<endl;return 0;}由于初始时是左闭右闭区间:所以可以while(left<=right){},然后在break中设置break条件即可，影响的就是Left=right的情况，貌似在这一题目中不会出现，因为肯定有解
- POJ 2456
题目大意：n个房子，m头牛，房子有一个横坐标，问将m头牛塞进房子，每两头牛之间的最大间隔是多少。
解题思路：
不难看出应该二分房子间隔，找一个最大的可行间隔。
首先将房子坐标排序，这样只需从第1个房子开始塞牛就行了，且第一个房子肯定得塞一只牛，才能保证空间的有效利用。
这样，每次对于一个间隔，从第一个房子开始塞牛：
①如果上一个房子坐标last+间隔<=h[i],那么这个房子肯定得塞牛，才能有效利用空间，更新last，cnt++。
②否则不能塞牛，去下一个房子。
这样，只要最后cnt>=m,这个间隔就是可行的。
设置d 属于区间[相邻区间的最小值, h[n-1] - h[0]]即可
我们可以看到二分求解是可以用来求最值问题的，只要发现求解的单调性，然后二分其解空间，并根据其是否符合题目中的条件来缩小解空间即可。
- 各种取值范围的问题
URAL Fibonacci Sequence
题意:给定Facc序列中的任意两个值，然后求另外的一个序列值。 采取递推的方式（求出系数）->求出两个相邻值->求解f(n)
列出f[i],f[j],f[i+1]的关系 ： f[j] = a[j-i-1]f[i+1] + a[j-i-2]f[i]
其中，a数列满足a[i]=a[i-1]+a[i-2],也是一个斐波那契数列，这里j-i>0，且i j已知，所以可以求得。采取二分查找（因为这个相邻值越大，那么最后递推得到的值也越大,而斐波那契数列是单调的）的方式->找到某个值的相邻值->求解f(n)
使用二分查找的方式比较简单的是不用long double这么大的数据类型来保存Facc序列中的系数值，只需要判断是否溢出，然后break掉就好啦！
比较的方式就是比如有一个数和f[i]构成相邻 然后递推到f[j]'和f[j]比较来确定解空间的移动，并且f的范围是[-2*10^9, 2*10^9]
补充:另外斐波那契数列的某一项除了O(n)的循环方式可以求解之外，还可以使用矩阵快速幂的方式进行求解，简化为O(logn)
基于以下性质:
证明通过数学归纳法即可证明
- 三分入门
URAL Bookshelf
使用三分来确定函数的最大值（但要保证此时函数的单调性）。
#include<iostream>#include<vector>#include<algorithm>#include<cmath>#include<iomanip>using namespace std;const double eps =1e-6;double h,H,L;double cal(double x){return H*x/(2*sqrt(x*x+h*h))-x;}int main(){cin>>h>>H>>L;double low=0,high=sqrt(H*H-h*h);while(fabs(high-low)>eps){double lmid=(low*2+high)/3;double rmid=(low+high*2)/3;if(cal(lmid)>cal(rmid))high=rmid;else low=lmid;}cout<<fixed<<setprecision(6)<<cal(low)<<endl;return 0;}
unsigned int 0～4294967295
int 2147483648～2147483647
unsigned long 0～4294967295
long 2147483648～2147483647
long long的最大值：9223372036854775807
long long的最小值：-9223372036854775808
unsigned long long的最大值：1844674407370955161
__int64的最大值：9223372036854775807（与long long相同）
__int64的最小值：-9223372036854775808
unsigned __int64的最大值：18446744073709551615
__int128:可以比long long 更大的整数值
double通常用来比较大小时通常需要设置一个微小值如1e-9
#define eps 1e-9(t2-t1)<=eps代表相等
double: 8 byte = 64 bit 范围：1.79769e+308 ~ 2.22507e-308
long double: 12 byte = 96 bit 范围： 1.18973e+4932 ~ 3.3621e-4932
float: 4 byte = 32 bit 范围： 3.40282e+038 ~ 1.17549e-038
一般用来表示最大值的为int 0x7fffffff,但有时最大值还需要用来比较，所以一般比这个要小一些。
二分例题两道:https://jecvay.com/2014/08/erfen-poj1064-poj2456.html
http://blog.csdn.net/area_52/article/details/44224633
二分求解平方根:
double x = sqrt(N);
double high = N;
double low = 0;
double mid = N / 2;
while (fabs(mid*mid-x) > 0.0001) { //永远不会出现越界的情况 不必处理
if (mid * mid > N) {
high = mid;
} else {
low = mid;
}
mid = (low + high) / 2;
}
return mid;
牛顿迭代法求平方根:
https://www.zhihu.com/question/20690553
这里要注意两点:
1. 
2. 需要满足的使用牛顿迭代的条件方可使用
3. 针对求方根有
代码如下:
int sqrt(int x) {
double ans = x;
double delta = 0.0001;
while (fabs(pow(ans, 2) - x) > delta) {
ans = (ans + x / ans) / 2;
}
return ans;
}
有序数组求第k大数的问题，
1. 有两个有序数组，长度相同，取中位数，
二分查找能够work的前提是因为
如果我们去掉数组比中位数小的k个数，再去掉比中位数大的k个数，得到的子数组的中位数和原来的中位数相同
v1[mid] = v2[mid], return mid
v1[mid] < v2[mid] 结果在v1[mid+1, n1-1]以及v2[0, mid-1]相当于淘汰了整体的前mid个和后mid个数字
v1[mid] > v2[mid] 结果在v1[0, mid-1]以及v2[mid+1, n2-1]中继续寻找
边界条件:
如果两个数组size相同的，最后的边界肯定是v1留下一个数字且v2留下一个数字的时候
变化:如果两个数组的size不同，在减的时候要减去一个相同的长度(选最小的截取)
边界条件: 如果总数奇数个的话，最后应该1/0或者0/1的情况，否则还是1/1的情况变化: 如果不选中位数了，而是选第k大的，可以发现问题的核心都是两个数组的前半部分一定要凑够k，同时在调整的时候，与前边不同了
include
include
using namespace std;
int a[1000005],b[1000005];
int find_kth(int A[],int m, int B[], int n, int k)
{
//始终保持A是小的，B是大的
if(m > n ) return find_kth(B, n, A, m, k);
if( m == 0) return B[k-1];
if( k == 1) return min(A[0], B[0]);int ia = min(k /2, m); int ib = k -ia; if( A[ia-1] < B[ib -1]) //删除小的左边的，也就是比k小的部分 return find_kth(A +ia, m -ia, B, n, k -ia); else if( A[ia-1] > B[ib-1]) return find_kth(A, m, B +ib, n -ib, k -ib); else return A[ia-1];}
