Eisen 筆記

#33. Search in Rotated Sorted Array

題目描述

有一組升序排列並且每個數值都是唯一的整數陣列nums。

在傳遞給你的函數之前，nums可能被從一個未知的位置k(1<=k<nums.length)進行了扭轉，所以陣列會形成[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](0-indexed)的形式。 舉例來說，[0,1,2,4,5,6,7]可能會被從位置3進行扭轉，因此變成了[4,5,6,7,0,1,2]。

給你一個可能被扭轉過的陣列nums以及一個整數target，如果target存在於陣列中則回傳整數的位置，反之則回傳-1。

你必須設計時間複雜度為O(log n)的演算法。

限制條件

  1. 1 <= nums.length <= 5000
  2. -104 <= nums[i] <= 104
  3. 所有數字都是唯一的。
  4. nums是一個升序排列的陣列，但是可能被扭轉過。
  5. -104 <= target <= 104

解題思路

這一題要解決扭轉後的陣列，但是實際上不需要去特別處理扭轉後的陣列。 二元搜尋法很單純，因此只要劃定好範圍就可以得到答案。

  1. 按照二元搜尋法的規則取得中間值的位置。
  2. 這個時候會被劃分為左右兩個部分，因為題目只扭轉過一次陣列，因此扭轉點不是在左邊就是在右邊，而其中的另外一邊的區間是按照正常升序排列的。
  3. 選取按照正常升序排列的區間，判斷target是否存在於這個區間中，如果存在則接下來完全按照二元搜尋的規則就可以找到答案了。
  4. 反之如果不存在的話，代表target落在有扭轉點的那半部，但是因為我們已經知道正常排序的部分了，因此也可以用二元搜尋規則繼續下去。
  5. 每一次的重複搜尋只要先找到正常排序的那半邊，就可以不用理會扭轉點的部分，只要判斷target是否存在就好了。
public class Solution {
    public int Search(int[] nums, int target) {        
        int left = 0;
        int right = nums.Length-1;
        while(left<=right){
            int mid = (left+right)/2;                        
            if(target==nums[mid]){
                return mid;
            }
            if(nums[mid]<=nums[right]){
                if(target>=nums[mid] && target<=nums[right]) left = mid+1;
                else right=mid-1;
            }
            else{
                if(target>=nums[left] && target<=nums[mid]) right = mid-1;
                else left=mid+1;
            }                       
        }
        return -1;
    }
}

複雜度分析：

  • 時間複雜度：O(log n)。
  • 空間複雜度：O(1)

學習重點

  • 二元搜尋
Last Updated:
Contributors: eisen