T33. Search in Rotated Sorted Array【Medium】

題目

假設(shè)有一個升序的數(shù)組以某個未知的支點旋轉(zhuǎn)。

（例如，0 1 2 3 4 5 6 7 可以變成 4 5 6 7 0 1 2）

假設(shè)這個數(shù)組中沒有重復的元素，給你一個 target(目標數(shù))，如果在這個數(shù)組中找到則返回它的 index，如果找不到就返回 -1

思路

首先，一般的有序的數(shù)組，查找一個數(shù)字一般都是用二分法，因為這樣比較有效率。

按題中說法旋轉(zhuǎn)數(shù)組后，分成的兩半仍然是排好序的數(shù)組。

例如，4 5 6 7 0 1 2，左邊的 4 5 6 7，以及右邊的 0 1 2 都是排好序的，可以先確定 target 在哪邊，然后繼續(xù)二分查找。不過這個代碼是從中間二分，分到的一半可能還是有兩段排序的代碼，需要繼續(xù)分，就是很神奇的代碼。

具體看代碼以及注釋~還是這句話，最好自己拿個例子試試，瞬間清晰！

信我 (? ??_??)? ！

代碼

代碼取自 Top Solution，稍作注釋

public int search(int[] nums, int target) {
        //定位數(shù)組頭和尾
        int start = 0;
        int end = nums.length - 1;
        //start > end時表示里面不包含了，跳出循環(huán)
        while (start <= end){
            int mid = (start + end) / 2;
            //找到匹配值，返回index
            if (nums[mid] == target)
                return mid;
            //通過nums[start] <= nums[mid]表明start~mid這段是正確升序的
            if (nums[start] <= nums[mid]){
            //這就是二分法的做法，判斷點在哪里，然后通過把start或者end賦予新的mid左右的值，表示選擇前一段或者后一段
                 if (target < nums[mid] && target >= nums[start]) 
                    end = mid - 1;
                 else
                    start = mid + 1;
            } 
            //通過nums[mid] <= nums[end]表明mid ~ end這段是正確升序的
            if (nums[mid] <= nums[end]){
             //這就是二分法的做法，判斷點在哪里，然后通過把start或者end賦予新的mid左右的值，表示選擇前一段或者后一段
                if (target > nums[mid] && target <= nums[end])
                    start = mid + 1;
                 else
                    end = mid - 1;
            }
        }
        //不存在的，返回-1
        return -1;
    }

補充

注意啦~這里是代碼里的東西要補充說一下！一開始不明白這代碼為什么要這么多if。

這里是有對應關(guān)系的，先判斷在 start~mid是升序的才能用 target < nums[mid] && target >= nums[start] ，來判斷 target 在不在這一段，然后若不是才說是在 mid ~ end的。（希望只有我一個人最開始第一眼沒有看出來 ╮(??? ????)╭...）

      if (nums[start] <= nums[mid]){
          if (target < nums[mid] && target >= nums[start]) 
               end = mid - 1;
          else
               start = mid + 1
      }