33. Search in Rotated Sorted Array


問題の説明


整数型配列numsは、繰り返しずに昇順に配列される.
関数の前にnumsは任意のpivotインデックスk(1<=k例えば、[0,1,2,4,5,6,7]はpivotインデックス3において[4,5,6,7,0,1,2]ループすることができる.
ループを完了する配列numsに、整数targetに、numsに存在するtargetのインデックスを検索します.存在しない場合は、-1が出力されます.
必ずO(logn)で時間の複雑さを実現しなければならない.

出力例



方法


初めての試み


一般的な二分探索では、ゼロインデックスの値を考慮すべきですか?
もう一つの基準を増やして実施する.
配列は増加してから減少してから増加する様子を呈している.
ターゲット値がnums[0]より大きい場合、ターゲット値は増加します.
ターゲット値がnums[0]を基準として小さい場合、増分後の最小値インデックスから最後のインデックスまでの間に存在します.
2つに分けた後、2つのナビゲーションの中間値(mid)とnums[0]を比較して、それらが同じようにどこにあるかを決定します.
そしてstartとend値を調整し、二分探索を行い、、、!

ソースコード

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start=0;
        int end = nums.size()-1;
        int mid;
        
        if(nums[0] > target){
            while(start <= end){
                mid = (start + end)/2;
                //증가하는 부분에 mid 위치
                if(nums[0] <= nums[mid]){
                    start = mid+1;
                }
              //증가했다가 감소하는 부분에 mid 위치
                else{
                    if(nums[mid] > target){
                        end = mid -1;
                    }
                    else if(nums[mid] < target){
                        start = mid+1;
                    }
                    else return mid;
                }

            }   
        }
        else if (nums[0] < target){
            while(start<=end){
                mid = (start + end)/2;
                //증가하는 부분에 mid 위치
                if(nums[0] <= nums[mid]){
                    if(nums[mid] > target){
                        end = mid -1;
                    }
                    else if(nums[mid] < target){
                        start = mid+1;
                    }
                    else return mid;
                }
                 //증가했다가 감소하는 부분에 mid 위치
                else{
                    end = mid - 1;
                }

            }
        }
        else return 0;
        
        
        return -1;
    }
};

レビュー


最初は問題が急に理解できなくなりました.コードを効率的に記述する方法が重要な問題のようです.
実行時間は4 msで悪くはありませんが、コードが汚いです.