二分查找.PPT

1、CUGB ACM/ICPC GROUP二分查找算法CUGB ACM/ICPC GROUP簡單定義：在一個單調(diào)有序的集合中查找元素，每次將集合分為左右兩部分，判斷解在哪個部分中并調(diào)整集合上下界，重復(fù)直到找到目標(biāo)元素。時間復(fù)雜度：O (logn)，優(yōu)于直接順序查找O(n)二分查找算法CUGB ACM/ICPC GROUP例子：CUGB ACM/ICPC GROUP /x：待查找的元素， n：數(shù)組集合大小， num數(shù)組單調(diào)遞增 int low=0,high=n,mid,res = -1; /low:集合下界 high：集合上節(jié) while(low=high) mid=(low+high)/2; /m

2、id:將集合分割為兩部分 if(nummid=x) /查找到符合元素x res = mid; break; else if(nummid 1.0e-6) mid = (high + low)/2; if(Caculate(mid)=4時v的最大值即可得到答案CUGB ACM/ICPC GROUP/由于精度差問題，考慮先將面積*1000000轉(zhuǎn)化為整數(shù)來二分 long long res,mid; while (low = high) mid = (high + low) / 2; if (judge(mid) ) low = mid + 1; res = mid; /最后結(jié)果為res else

3、high = mid - 1; 核心代碼bool judge(long long mid) long long p = 0; for (int i = 0; i = f;CUGB ACM/ICPC GROUP推薦題目推薦題目Poj 3273 ,1434Hdu 2141 ,2899,1969Coj 1080 ,1216,1048CUGB ACM/ICPC GROUP 當(dāng)需要求某凸性或凹形函數(shù)的極值，通過函數(shù)本身表達式并不容易求解時，就可以用三分法不斷逼近求解。三分法CUGB ACM/ICPC GROUP類似二分的定義Left和Rightmid = (Left + Right) / 2midmid

4、 = (mid + Right) / 2;如果mid靠近極值點，則Right = midmid；否則(即midmid靠近極值點)，則Left = mid;三分法CUGB ACM/ICPC GROUP精選可編輯ppt13例子：ZOJ 3203 Light Bulbhttp:/ ACM/ICPC GROUPdouble mid, midmid;while ( low + eps cmidmid ) high = midmid; else low = mid;核心代碼double cal(double x) return (h * D - H * x) / (D - x) + x; /這里放要求的函數(shù)； CUGB ACM/ICPC GROUP對于求解一些實際問題