704 二分查找

最重要的就是分類討論好二分盏浇，二分看著好寫邊界case還是需要測試的。大家需要注意二分的幾種情況

• 當(dāng)l = 0, r = n的時候因為r這個值我們在數(shù)組中無法取到,while(l < r) 是正確寫法

• 當(dāng)l = 0, r = n - 1的時候因為r這個值我們在數(shù)組中可以取到,while(l <= r) 是正確寫法 主要看能不能取到這個值

• 二分法有多種寫法芽狗，末尾是開區(qū)間閉區(qū)間都可以解出尋找單個元素和尋找邊界的題目绢掰，只需要注意相應(yīng)的是l < r還是l <= r,每次取mid還是取mid加減一即可。建議理解后背熟一套模板，不要搞混滴劲。

• 關(guān)于二分法和移除元素的共性思考

關(guān)于二分法和移除元素的共性思考這兩題之間有點類似的谊却，他們都是在不斷縮小 left 和 right 之間的距離，每次需要判斷的都是 left 和 right 之間的數(shù)是否滿足特定條件哑芹。對于「移除元素」這個寫法本質(zhì)上還可以理解為，我們拿 right 的元素也就是右邊的元素捕透，去填補 left 元素也就是左邊的元素的坑聪姿，坑就是 left 從左到右遍歷過程中遇到的需要刪除的數(shù)，因為題目最后說超過數(shù)組長度的右邊的數(shù)可以不用理乙嘀，所以其實我們的視角是以 left 為主末购，這樣想可能更直觀一點。用填補的思想的話可能會修改元素相對位置虎谢，這個也是題目所允許的盟榴。

• 其實二分還有很多應(yīng)用場景，有著許多變體婴噩，比如說查找第一個大于target的元素或者第一個滿足條件的元素擎场，都是一樣的，根據(jù)是否滿足題目的條件來縮小答案所在的區(qū)間几莽，這個就是二分的本質(zhì)迅办。另外需要注意，二分的使用前提：有序數(shù)組

• 小tips：

• 根據(jù)題目的數(shù)據(jù)量范圍選擇合適的算法章蚣，比如數(shù)據(jù)量是10^{5站欺，那就只能使用O(nlogn)復(fù)雜度以下的算法了，使用O(n}2)是會超時的纤垂；而如果數(shù)據(jù)量只有100或者1000矾策，則可以果斷的采用暴力方法（一般是O(n^2)）進行求解

• 二分的最大優(yōu)勢是在于其時間復(fù)雜度是O(logn)，因此看到有序數(shù)組都要第一時間反問自己是否可以使用二分峭沦。

例題講解

左閉右閉版

二分查找.png

若要對該數(shù)組進行二分查找要注意以下兩點易錯點：

1. while 循環(huán)變量中 left <= right贾虽。記住一定是小于等于而不是小于這是因為我們寫的是左閉右閉版 left 是可以等于 right 的。

2. 當(dāng)比較發(fā)現(xiàn) nums[mid] 的值小于 target 的值時吼鱼， 跟新右區(qū)間的左邊界榄鉴，left = mid + 1 ! ! !。而不是 left = mid 再次強調(diào)我們的區(qū)間是左閉右閉的蛉抓。我們已經(jīng)判斷出 nums[mid] 的值小于 target 了庆尘，說明 muns[mid] 一定不是我們搜索的值，接下來搜索的區(qū)間一定不包含這個數(shù)值巷送。

代碼如下：

class Solution {
    public int search(int[] nums, int target) {
        //左閉右閉
        int left = 0;
        int right = nums.length - 1;
        int mid;
        while( left <= right ){
            mid = (left + right) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }
            else if(nums[mid] > target){
                right = mid - 1;
            }
            else return mid;
        }
        return -1;
    }
}

27 移除元素數(shù)值

關(guān)鍵是要理解 fast 和 slow 指針的作用驶忌。fast 指針用來尋找新數(shù)組中需要的元素，slow 指針用來指明新數(shù)組下標(biāo)的位置。我們把 fast 指針?biāo)@取的值賦值給新數(shù)組所對應(yīng)下標(biāo)的位置付魔。

27移除元素.png

代碼如下：

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for(int fast = 0; fast < nums.length ; fast++){
            if(nums[fast] != val){
                nums[slow ++] = nums[fast];
            }
        }
        return slow;
    }
}