leetcode 6. 秩序配列が回転した後にSearch in Rotated Sorted Arrayを検索する

Search in Rotated Sorted Array難易度: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.
(次の問題では重複する場合の研究を行うSearch in Rotated Sorted ArrayII)
問題を解く構想:配列探索問題に対して、時間複雑度は大体3種類のO(n)、O(lg n)、O(1)の中で線形複雑度O(n)、すなわち順序探索がある.定数時間O(1)は一般にキーワードインデックスまたはHashテーブルによって実現される.対数複雑度O(lg n)は、よく二分検索、二叉検索ツリータイプによって実現される
この問題の条件は秩序配列の変形であるため、「高速ソートの選択」-二分検索の難点は、分割要素と分割要素の左右の再帰条件とその境界を探すことである.
分割要素の場合、中間m = (l+r) / 2;配列境界[l,r)を直接取ることが容易に考えられる.実例観察:可能なすべてのケースを探す能力を強化しなければならない0 1 2 4 5 6 7 0 1 2 5 1 3 1 nums[m]>nums[m]:(l,m-1)単増nums[m]<=nums[l]:(m+1,r)単増注:-配列が境界[l,r)を取ると、mは中央右側(例えば2要素の場合、m=1)に取るしたがって、この場合nums[m],num[l]−配列境界[l,r]をとると、mは中央より左(2つの要素の場合、m=0)に取られるので、nums[m],num[r]を比較すべきである.
配列境界は[l,r)−O(lg n)である

class Solution {
public:
    //nums       [l,r)
    int searchR(vector<int>& nums,int l, int r, int target) {
        if (r <= l)
            return -1;
        int m = (l+r) / 2;
        if (nums[m] == target)
            return m;

        if (nums[l] < nums[m]) {
            if (target >= nums[l] && target < nums[m])
                return searchR(nums, l, m, target);
            else
                return searchR(nums, m+1, r, target);
        } else {
            if(target > nums[m] && target <= nums[r-1])
                return searchR(nums, m+1, r, target);
            else
                return searchR(nums, l, m, target);    
        }
    }

    int search(vector<int>& nums, int target) {
        return searchR(nums, 0, nums.size(), target);
    }
};

配列境界[l,r]–配列に入力される境界に注意

class Solution {
public:
                    //nums       [l,r]
    int searchR(vector<int>& nums,int l, int r, int target) {
        if (r < l)
            return -1;
        int m = (l+r) / 2;
        if (nums[m] == target)
            return m;

        if (nums[r] > nums[m]) {
            if (target > nums[m] && target <= nums[r])
                return searchR(nums, m+1, r, target);
            else
                return searchR(nums, l, m-1, target);
        } else {
            if(target >= nums[l] && target < nums[m])
                return searchR(nums, l, m-1, target);
            else
                return searchR(nums, m+1, r, target);    
        }


    }
    int search(vector<int>& nums, int target) {
        return searchR(nums, 0, nums.size()-1, target);
    }
};

シーケンス検索O(n)–推奨されません

class Solution {
public:

    int search(vector<int>& nums, int target) {
        int i = 0;
        for (; i < nums.size(); i++) {
            if (nums[i] == target)
                break;
        }
        if(nums.size() == i)
            return -1;
        else
            return i;
    }
};

(次の問題では重複する場合の研究を行うSearch in Rotated Sorted ArrayII)