標(biāo)簽： C++ 算法 LeetCode 數(shù)組 困難 二分法

每日算法——leetcode系列

問題 Search in Rotated Sorted Array

Difficulty: Hard

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        
    }
};

翻譯

在旋轉(zhuǎn)排序數(shù)組中搜索(指定的目標(biāo))

難度系數(shù)：困難
假定一個(gè)有序數(shù)組在一個(gè)預(yù)先不知道的軸點(diǎn)地方被旋轉(zhuǎn)。
例如，0 1 2 4 5 6 7可能會(huì)變?yōu)?code>4 5 6 7 0 1 2。
給你一個(gè)目標(biāo)值去搜索，如果在數(shù)組中找到了則返回它的索引，否則返回-1。
你可以假定數(shù)組中沒有重復(fù)的元素。

思路

對(duì)于有序數(shù)組， 查找可以用二分查找，但由于是事先不知道在什么地方旋轉(zhuǎn)過的，一開始想法簡(jiǎn)單粗暴， 找出旋轉(zhuǎn)的軸點(diǎn)位置， 再把他旋轉(zhuǎn)回有序狀態(tài)， 再二分查找，最后再用旋轉(zhuǎn)后跟旋轉(zhuǎn)前的索引對(duì)應(yīng)關(guān)系找到index。這個(gè)時(shí)間復(fù)雜度有點(diǎn)高。

直接分析旋轉(zhuǎn)后的數(shù)組：
假定start, end, mid分別代表起始、末尾、中間索引
二分法思想：

• 如果 nums[mid] == target, 找到， 如果沒找到則確定target所在的索引范圍
• 如果 nums[start] <= num[mid]

1. 可以證明start到mid是有序的且不存在滿足nums[start] <= x <= num[mid]的x在start和mid的外邊（反證法）
   如果是target也滿足nums[start] <= target <= num[mid]， 那么target的索引在start和mid間
2. 同理可以證明如果target不滿足上面的不等式， 那么target的索引在mid+1和end之間

• 如果 nums[start] > num[mid]

1. 可以證明mid+1到end是有序的且不存在滿足nums[mid+1] <= x <= num[end]的x在mid和end的外邊（反證法）
   如果是target也滿足nums[mid+1] <= target <= num[end]， 那么target的索引在mid+1和end之間
2. 同理可以證明如果target不滿足上面的不等式， 那么target的索引在start和mid之間

代碼

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