33.Search in Rotated Sorted Array I && II

一個遞增的數列, 會作旋轉

這我們要怎麼做呢, 我們一樣用二分搜尋法, 不同的是, 我們每次都會先分成兩邊, 一邊是有序的, 另一邊未知, 可能有序, 也可能無序

要怎麼確認一邊有序呢, 很妙的, 將得到中間的值, 跟最右邊的值做對比, 倘若中間的值較小, 及右半邊是有序的, 反之則是左半邊, 一開始很那們, 這樣到底跟二分搜尋法差在哪, 為什麼要做這種判別

可以了解到, 我們會對兩個半邊做淘汰, 但你得先知道你要的數字在哪半邊,充其量就是把範圍縮小而已,是不是很容易搞混

當有一個值為

[1,3], target = 3

會發現, 第一次mid的值為1, 所以檢查是否小於最後一個值3, 是

但我們的目標是三, 這個舉動會讓他永遠找不到, 所以檢查的小於, 要改成小於等於

另一邊反之亦然

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

這樣即可完成

再來第二版變化了一下, 上一題是不會出現重複的數字, 這邊開始會重複, 但相對只需要判斷是否target在陣列裡面

我們很快的用上一題的思維下去寫

class Solution {
  public:
    bool search(vector<int> &nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[mid] < nums[right]) { // right hand side are sorted
                if (nums[mid] > target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            } else {
                if (nums[mid] < target && target >= nums[left]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
        }
        return false;
    }
};

恩, 看起來沒有什麼問題, 但是在面對以下的case 會發生一種狀況

[2,5,6,0,0,1,2]
3

當循環到最後, left的值為3, right的值也為3, 對應到的數字是0

但上面的方式會一直不段的死循環下去, 等於是當mid跟right的值一樣, 我們沒有辦法判斷

其實只要加一個判斷, 當mid跟right值一樣時, right往左移一個就行了

class Solution {
  public:
    bool search(vector<int> &nums, int target) {
        int l = 0;
        int r = nums.size() - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[mid] < nums[r]) {
                if (nums[mid] < target && nums[r] >= target) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            } else if (nums[mid] > nums[r]) {
                if (nums[mid] > target && nums[l] <= target) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                r--;
            }
        }
        return false;
    }
};

想分享一下對這題的看法, 一般我們理解的二分搜尋法非常淺顯易懂, 就是在一個以排序的陣列找大小

但這邊的做法就是從兩邊中選一邊, 一直選到結束

也是另類的二分搜尋的變化