【LeetCode】33.Search in Rotated Sorted Aray解題報告（Python&C+）

作者：负雪明ろうそくid：fuxuemingzhu個人ブログ：http://fuxuemingzhu.cn/
目次

テーマ記述

タイトルの大意

解題方法

日付

タイトルの住所:https://leetcode.com/problems/search-in-rotated-sorted-array/description/
テーマの説明
Suppose an array sorted in ascending order 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 arrary return its index，otherswise return -1.
You may asumeのduplicate exists in the array.
Your algorithm’s runtime coplexity must be in the order of O(log n).
Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

タイトルの大意
回転順序配列の中にある値が含まれているかどうかを探し出し、ある場合は番号を返します。そうでなければ-1を返します。
問題の解き方
明らかに二分検索ですが、何度も間違えました。この問題で重要なのは、midと左右のポインタが指す値の比較ではなく、ポインタを移動させることです。その部分が秩序化していると判断することによって、ターゲットはこの規則的なスライスの中にあるかどうかを判断することによって実現される。
この問題は私達に二点検索に対してより深い理解をさせます。
私達の二点検索の思想はある条件を探し出すことです。この条件は私達に左右のポインタを移動させる参考を与えました。つまり、検索したtargetはmidの左か右かを判断します。具体的には、与えられた配列が回転秩序であるため、midがpivotの位置を指している場合、midの後ろの部分が整然としています。この場合、targetはmidの左側か右側かを判断する必要があります。最も簡単な方法は、targetが「pivot，r」の区間内にあるかどうかを判断することです。midの左半分を検索します。これと同じように、midがpivotの前にいると、midの前の部分は規則的であり、下の方はmidの左側か右側かをtargetによって判断する。
以下の解答は以下の通りです。http://blog.csdn.net/linhuanmars/article/details/20525681
具体的には、配列がAであると仮定し、左の端がlであり、右の端がrであり、中間の位置がmである。反復のたびに、3つの状況に分けられます。
（1）もしtarget==A[m]だったら、mは私達が必要とする結果です。直接に戻ります。（2）A[m]なら（3）A[m]==A[r]の場合は、lからmまでは必ず規則的であり、同様にターゲットがこの範囲内にあるかどうかを判断するだけで、該当するエッジを移動すれば良い。
なお、この問題はエッジ要素との判断を行うため、[l，r]の左閉右開区間ではなく[l，r]双閉区間が使われています。

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums: return -1
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) / 2
            if nums[mid] == target:
                return mid
            if nums[mid] < nums[right]:
                if target > nums[mid] and target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            else:
                if target < nums[mid] and target >= nums[left]:
                    right = mid - 1
                else:
                    left = mid + 1
        return -1            

C++コードは以下の通りです

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

日付
2018年3月12日2019年1月11日ーー小光棍節？