二分-不止是查找哦

二分過程：首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。（摘自百度百科）

很顯然，使用二分查找需要滿足兩個要求

1.必須采用順序存儲結構。

2.必須按關鍵字大小有序排列。

?

不斷縮小一半的范圍，所以時間復雜度O(logn).

貼出有序數組中二分查找的代碼

int bsearchWithoutRecursion(int array[],int low,int high,int target) {while(low<=high){int mid=low+(high-low)/2;/*使用(low+high)/2會有整數溢出的問題（問題會出現在當low+high的結果大于表達式結果類型所能表示的最大值時，這樣，產生溢出后再/2是不會產生正確結果的，而low+((high-low)/2)不存在這個問題*/if(array[mid]>target)high=mid-1;else if(array[mid]<target)low=mid+1;else return mid;}return-1; }

一、淘汰一半即可

進一步：二分搜索算法不一定只能在有序數組中進行，只要你在查找的時候發現可以很確定的淘汰數組的一半，留下另一半，那么都是可以用二分搜索的。

來一道水題來說明。

題目描述

把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。 輸入一個非減排序的數組的一個旋轉，輸出旋轉數組的最小元素。 例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。 NOTE：給出的所有元素都大于0，若數組大小為0，請返回0。

鏈接https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=11159&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

思路：因為旋轉過去的都大于右邊的。

設左右端點，中間位置大于右邊說明中間位置為旋轉過去的，最小值在右邊，向右繼續查找；

否則說明中間位置為未旋轉區域，最小值在左邊，向左查找。

?

繼續

來看題：

?

本題一般思路：依次查找找到比前后都小的數；或者選出最小數，他肯定是局部最小的；等等

但這些都是O(n)的方法，而用二分可以做到O(logn).

二分思路：

? 考慮最左和最右的元素：如果arr[0]<arr[1] ?return?0; arr[N-1]<arr[N-2] return?N-1;

? ?考慮最中間元素，如果中間元素大于它左邊的元素，那么局部最小值就應該在數組的左半部分

? ?如果中間元素小于大于它右邊的元素，那么局部最小值就應該在數組的右半部分

? ?中間元素既小于它左邊的值又小于它右邊的值，那么它就是局部最小

最大化或最小化問題

如果在求解最大最小問題中，能比較簡單的判斷某個解是否滿足條件（這里的簡單一般指的是o(n)及以下，視具體數據范圍而定），使用二分搜索答案就能很好的解決問題。

舉個例子，POJ1064

題目鏈接：http://poj.org/problem?id=1064

題目大意：有n條繩子，長度分別為L[i]。如果從他們中切割出k條長度相同的繩子的話，這k條繩子每條最長能有多長？（答案保留小數點后兩位，規定1單位長度的繩子最多可以切割成100份）。

思路：二分搜索答案，每條最短0，最大設置一個較大的數，然后開始二分答案并依次判斷，判斷也很簡單，判斷每個繩子的長度整除答案的累加和是不是大于k就好了。

?

#include <cstdio> #include <cmath> using namespace std; const int M=10005; const double inf=200005.0; double L[M]; int n,k; bool judge(double x)//判斷解是否可行 {int num=0;for(int i=0;i<n;i++)num+=(int)(L[i]/x);return num>=k; } void solve()//二分答案 {double left=0,right=inf;for(int i=0;i<100;i++) //代替while(r>l) 避免了精度問題{ //1次循環可以把區間縮小一半，100次可以達到10^(-30)的精度double mid=(left+right)/2;if(judge(mid)) left=mid;else right=mid;}printf("%.2f\n",floor(right*100)/100); } int main() {while(scanf("%d%d",&n,&k)!=-1){for(int i=0;i<n;i++)scanf("%lf",&L[i]);solve();} }

POJ2456

題意：

有n個牛欄，選m個放進牛，相當于一條線段上有 n 個點，選取 m 個點，

使得相鄰點之間的最小距離值最大

思路：和上一道題類似，二分答案，判斷答案也很簡單，貪心即可，遍歷，遇到大于枚舉的距離就放一只牛，看最后能不能放得下。

代碼不貼了

?

最大化平均值

剛開始做這種題的時候，只知道沒有按單位價值貪心那么簡單，因為物體質量越大它占的比重越大，對總體的影響就越大。單位價值=總價值/總質量，

?

?

?

?

?

?

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的二分查找及一般拓展总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。