二分查找

二分查找的大體模闆很簡單，但是上課的時候看到結束條件下邊界和上邊界有時候相等有時候不等；mid有時候加一有時候不加一；本來感覺沒什麼太大的意義；後來問了百度才知道，細節是魔鬼！

二份查找的基本架構

int Search(int *num, int target) {
    int left = 0, right = ...;
    while(...) {
        int mid = (right + left) / 2;
        if (num[mid] == target) {
            ...
        } else if (num[mid] < target) {
            left = ...
        } else if (num[mid] > target) {
            right = ...
        }
    }
    return ...;

下面從兩個方面細說

尋找一個數、尋找邊界；

尋找一個數

問題大概是

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

int Search(int*num, int target) {
    int left = 0; 
    int right = num.length - 1; //
    while(left <= right) { // 注意
        int mid = (right + left) / 2;
        if(num[mid] == target)
            return mid; 
        else if (num[mid] < target)
            left = mid + 1; // 注意
        else if (num[mid] > target)
            right = mid - 1; // 注意
        }
    return -1;
}

有兩個值得注意的細節

1是結束條件 left <= right 因為我們right = num.length - 1;即r=最後一個元素當然前提是從num【0】開始輸入的； left <= right 就是周遊的區間【l，r】是閉區間；

如果是 left < right就是開區間【l，r）；顯然最後一個元素别遺漏了；但是如果我right = num.length；那麼就代表開區間【l，r）r是最後一個元素再後一個；

這樣子就可以把最後一個元素包括了

2 mid是否加一

本題因為 num[mid]有三種情況是以當num[mid]=目标的時候就輸出了；也就是說num[mid]這個值已經被周遊了不用再繼承了；

但是尋找邊界的時候情況又不同；

尋找邊界

左邊界

int left(int*nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意

    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

需要注意的細節

1 while(left < right) 因為r是最後一個元素的下一個；是以用開區間就可以；

2 left = mid + 1，right = mid 因為我們的搜尋區間是 [left, right) 左閉右開，是以當 nums[mid] 被周遊之後，下一步的搜尋區間應該去掉 mid 分割成兩個區間，即 [left, mid) 或 [mid + 1, right)。剛好把mid給去掉

if (nums[mid] == target)

right = mid;

意思是把上邊界改成mid 因為 mid已經符合條件了但不一定是最左邊的邊界；是以這樣從left到mid來周遊，看有沒有其他邊界；沒有或者有都輸出left 有統一性；因為有另一個邊界的時候和沒有循環結束的條件都是left=right；這樣子就找到最左邊的邊界了

下面給出例題

是尋找邊界的變例區間由整數集變成連續的小數集

HDU 1551 Cable master

将n根網線切成k段相同長度的網線，問可切成的最長長度是多少；

思路：利用二分發查找答案，每次偏右查找（因為要查找大的）也就是查找右邊界；

sum = sum/k;
        double l = 0,r = sum;
        while(fabs(l-r)>exp)
        {
            double mid = (l+r)/2;
            if(judge(mid))
                l = mid+1;
            else
                r = mid;
        }
        printf("%.2f\n",l-1);
    }

    return 0;
}
int judge(double s)
{
    int cnt = 0;
    for(int i = 0; i<n; i++)
    {
        cnt+=(int)(a[i]/s);
    }
    if(cnt>=k) return 1;
    return 0;
}

1周遊區間是有小數的形式是以不能用大于或者大于等于的這種形式這樣不夠精确

2因為我們初始化 right = sum；

是以決定了我們的「搜尋區間」是 [left, right)

是以決定了 while (left +10e-6< right)

同時也決定了 left = mid 和 right = mid

因為我們需找到 target 的最右側索引

是以當 cnt== target 時不要立即傳回

而要收左側邊界以鎖定右側邊界

又因為收左側邊界時必須 left = mid 而不是left = mid+1；這是因為區間是連續的不是離散的整數；

3傳回 left

傳回right可能會出錯可能恰好left+10e-6越界了；

細節決定ac！

2021-05-16二分查找

二分查找

尋找一個數

尋找邊界