binary search

二分搜索說簡單也算簡單 說難也算難 有時寫不好 就會變成無窮迴圈
關鍵在哪裡呢  讓我來介紹一下巴

二分搜索的原理很簡單 就是針對以排序數列 利用比大小 每次捨去一半數列

至於為何會寫不好呢 有個小技巧可以克服 就是利用開閉區間的概念

開區間  (a,b) 意思是數會在a,b間  但不等於a 也不等於b
閉區間  [a,b] 意思是數會在a,b間  但可以等於a 也可以等於b

搞懂了這個之後  我們來看一道題: 連結
題目是從leetcode來的
題意是給一以排序數列,插入值為target的數,維持依然排序,返回插入點

先看兩端開區間寫法:
可注意到left取-1, right取總數,剛好確保為開區間

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=-1;
        int right=nums.size();
        int mid;
        while(right-left>1)
        {
            mid=(left+right)/2;
            if(target>nums[mid])
                left=mid;
            else if(target<nums[mid])
                right=mid;
            else
                return mid;
        }
        return left+1;
    }
};

再看兩端閉區間寫法:

可注意到left取0,right取數量減一,因為允許區間和數字相等,所以取數列兩端點,
終止條件也完全不同,允許>=,因為閉區間本來就允許兩端相等,此外每次更新也不同,
left=mid+1 和 right=mid-1 因為閉區間允許相同 所以每次可往前推進一個
最後就是return的也不同 因為left是確定至少會大於等於這個數 所以返回left

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        int mid;
        while(right>=left)
        {
            mid=(left+right)/2;
            if(target>nums[mid])
                left=mid+1;
            else if(target<nums[mid])
                right=mid-1;
            else
                return mid;
        }
        return left;
    }
};

總結:
搞懂了以上概念後 還可以自行變化 比如說 [ ) or ( ], 原理和上面也差不多,就自己嘗試囉