一：二分查找演算法

本文章列出刷題中常用的二分查找場景：尋找一個數、尋找左側邊界、尋找右側邊界，

1:1二分查找框架

int binarySearch(int[] nums, int key) {
    int left = 0, right = ...;

    while(...) {
        int mid = (right + left) / 2;
        if (nums[mid] == key) {
            ...
        } else if (nums[mid] < key) {
            left = ...
        } else if (nums[mid] > key) {
            right = ...
        }
    }
    return ...;
}

分析二分查找的一個技巧是：不要出現 else，而是把所有情況用 else if 寫清楚，這樣可以清楚地展現所有細節.

但是元素必須是有序的建議

建議計算mid防止溢位

 mid = (l + r + 1) / 2;

1.2尋找一個數

搜索一個數，如果存在，回傳其索引，否則回傳 -1，

    public class BinarySearch
    {
        public static int bs(List<int> data, int key)
        {
            int low = 0, mid = 0;
            int high = data.Count - 1;
            while (low <= high)
            {
                mid = (low + high) / 2;
                if (data[mid] == key)
                {
                    return mid;
                }
                else if (data[mid] > key)
                {
                    high = mid - 1;
                }
                else if (data[mid] < key)
                {
                    low = mid + 1;
                }
            }
            return -1;
        }
    }

一個有順序的陣列,我要找一個東西,我直接切一半,我要找的小了我就往左跑,大了我就往右跑，重復....，

PS：最差的情景比較次數是:Log2(n+1),這個是運氣真的差.且期望時間復雜度是O(Log2n).很慘

一種是兩端都閉的區間,一種是只閉一端的區間，問題點如果索引大小為length是越界的，上述代碼為兩端都閉的區間

顯而易見調出條件為找到目標值就可以終止

   if (data[mid] == key)
   {
        return mid;
   }

如果沒找到，就需要 while 回圈終止，然后回傳 -1

當前是當前集合或者陣列內沒有搜索的數字

1： while(left <= right) 的終止條件公式則為 [last,last-1], 例如：10000 ，9999 你的搜索區間直接為空，但此時while直接就終止了，因為你的搜索空間只有1，可見這時候搜索區間為空，沒有數字即>=1000 又<=9999，所以while終止

2：另外一種情況,你寫個left < right ，公式則為[last,last]，如10000,10000，直接沒有搜索區間，只有一個10000，這個區間[10000,10000]，不會被搜索,這個索引[10000]沒有被搜索的，這樣你就寫了bug -->

 return  nums[first] == key? first: -1;

1.3 尋找邊界的二分搜索

1.3.1 尋找右邊界的二分搜索

再次強調：二分的最終的一個目的就是刪掉不存在答案的區間，

如圖：如果這個我要找滿足包含（可以理解為>=4）4的值，這種情況可以抽象為一個模型,滿足的都為1，不滿足的都為0. 只要找到第一個就是答案

先初始化好兩邊的左右區間 ,現在需要變化一下while 的初始條件，

while(L!=R){
   int mid=（L+R）/2;
   L=mid+1
   R=mid
}

注解：

這樣看圖你的右邊一定都是1，所以應該動的是last 指標讓他指過來

有一種可能是 mid 也是可能是答案的，所以這個mid就不能刪，所以Last 指標直接指mid，只刪掉一定不存在答案的區間->所以動last指標，

為什么你指向的first->是+1

如果回圈在跑一次你的mid就指向了0了，而左邊都是0，一定不是答案，所以first=first+1.

結論是：左右指標重合時，就是第一個1

1.1.2 ：尋找左側邊界的二分搜索

如上文得出的模型,與上文相反，這個是需要找最后一個1.

while（L!=R）{
   int mid =(L+R+1)/2；
   L=mid；
   R=mid-1；
}

如果mid指向了1，則左邊都是1，同理這個mid 也可能是最終答案，不能洗掉，

下次回圈時L指向了這個mid，此時在求出一個mid,則應該動右邊的指標，

多次回圈最終形成了這個樣子，則在需要求一個mid =（f+l）/ 2 則指向了左指標也就指向了mid,如果在動左指標，左指標還此處，（現在就死回圈了）

為了避免這個事情，提前給它+1，當遇到上文死回圈時,則他就會指向了右邊（L），而且右邊一定不是答案，而L(R)=mid-1 又回到了F(F)這里.

此時左右重合就找了答案

下個目標為斐波那契查找和插值查找

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/499869.html

標籤：其他

上一篇：機器學習-Kmeans

下一篇：[LC1260]二維網格遷移