你覺得一個演算法難，是因為你的大腦對未知世界的恐懼，——yxc
簡單講講二分
- 二分是什么？
顧名思義：就是一分為二 (?)
它是一種在有序陣列中查找某一特定元素的搜索演算法
- 怎么搜索呢？
其實就是不斷取中間位置的值(簡稱中間值) 和目標值v比較
如果中間值大于v 那么v肯定在中間值的左區間 那就更新右邊界 繼續取中間值進行比較
如果中間值小于v 那么v肯定在中間值的右區間 那就更新左邊界 繼續取中間值進行比較
然后一直如此回圈直到找到目標值（目標值存在的前提下）
- 那么為什么要二分呢？
先舉個例子：
在一組有序數列 2 3 4 5 6 7 8 9 23 34 45 56 67 中 找到56的位置
樸素做法：
從第一個依次向后列舉 判斷是否為目標值 那么我們需要查詢12次
二分大法：
第一次取第(1+13)/2=7個數即8 8<56
第二次取第(8+13)/2=10個數即34 34<56
第三次取第(10+13)/2=11個數即56 56==56
由上可見 二分需要比較的次數僅僅只有樸素做法的四分之一
這還僅僅是只有13個數的數列
那么當資料很大時 有成千上萬個數時 二分查找的效率完虐樸素做法
這就是使用二分的原因
那么當數列中有多個重復目標值元素時 我們想找到第一個出現或者最后應該出現的位置時 該怎么辦呢
我們只要對 mid的取值和邊界的更新方式 稍微處理一下就能輕松應對啦！
這點很重要哦 下面給出模板
模板1、2都能用于查找無重復目標值
模板1:
查找上界
int max_vis(int l, int r, int v)
{
int mid;
while(l<r)
{
mid=(l+r+1)>>1;
if(b[mid]<=v) l=mid; //找到目標值時 左邊界不斷向右偏移
else r=mid-1; //
}
if(b[l]!=v) return -1; //如果不存在目標值回傳-1
return l;
}
模板2：
查找下界
int min_vis(int l, int r, int v)
{
int mid;
while(l<r)
{
mid=(l+r)>>1;
if(b[mid]>=v) r=mid;//找到目標值時 右邊界不斷向左偏移
else l=mid+1;
}
if(b[l]!=v) return -1;//如果不存在目標值回傳-1
return l;
}
注意：
-
mid取(l+r)>>1時 對應的邊界處理：l=mid+1;r=mid;
-
mid取(l+r+1)>>1時 對應的邊界處理：l=mid;r=mid-1;
(l+r)>>1取值靠向左邊界 （l+r+1）>>1取值靠向右邊界
mid取值要多加注意，否則會導致漏答案或死回圈的結果，
自己可以試著模擬一下
可簡記為：
在查找上界時，左邊界不斷向右偏移 尋找目標值的最大位置(l=mid），
到達最大位置時，右邊界撞向左邊界(r=mid-1),直到重合退出回圈，
-->左偏移右撞
在查找下界時，右邊界不斷向左偏移 尋找目標值的最小位置(r=mid），
到達最小位置時，左邊界撞向右邊界(l=mid+1),直到重合退出回圈，
-->右偏移左撞
我稱之為:
移撞大法!
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/516398.html
標籤：其他
上一篇：本科畢設選題