LeetCode-回転配列の検索

LeetCode-回転配列の検索
くだらないことは言わないで、先に住所を教えてください.
https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
昇順で並べ替えられた配列が予め未知の点で回転していると仮定する.
(例えば配列[0,1,2,4,5,6,7]は[4,5,6,7,0,1,2]になる可能性がある).指定したターゲット値を検索し、配列にターゲット値が存在する場合はインデックスを返します.そうでない場合は-1を返します.配列に重複する要素が存在しないと仮定できます.あなたのアルゴリズムの時間複雑度はO(log n)レベルでなければなりません.例1:入力:nums=[4,5,6,7,0,1,2]、target=0出力:4例2:入力:nums=[4,5,6,7,0,1,2]、target=3出力:-1
まず本題の構想を与え,配列が回転しなければ簡単な二分検索であり,本題の境界線を見つけることができれば二つの二分検索に変えることができる.二分検索自体は時間の複雑さの要求に合致している.では問題の鍵は、配列内の回転位置を見つけることになります.ここも同じように二分で探します.配列left mid right 4,5,6,7,0,1,2に対してこの配列を二分すると以下の2つのケースがあり,4-7の区間のある位置に落ち,0-2の区間に落ち,4-7の表現がnums[mid]>=nums[left]かつnums[mid]>=nums[right]であれば,ここでleft==rightが現れる可能性があると思ったら、左区間はleft=mid+1、右区間であればright=mid-1ですが、ここでは回転位置かどうかを先に判断し、境界置換を行うことに注意してください.移動すると回転位置になるからです.では、回転位置の特徴は何でしょうか.nums[mid]>nums[mid-1]注意mid>=1.次に、回転位置ルックアップコードを示します.

        def binary_search_min_index(self,nums):

        if not nums:
            return -1
        left = 0
        right = len(nums) - 1

        while left <= right:
         # python 3         3 / 2 = 1
            mid = (left + right) // 2
            #       
            if mid >= 1 and nums[mid] < nums[mid - 1]:
                return mid

            if nums[mid] >= nums[right] and nums[mid] >= nums[left]:
                left = mid + 1
            else:
                right = mid - 1
        return -1

返される数字は配列中の回転位置の下付き文字で、下付き文字によって2つの秩序ある配列に分割して二分検索すればよい.

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        
        if not nums:
            return -1
        left = 0 
        right = len(nums) - 1
        #         index
        index = self.binary_search_min_index(nums)
        #           
        if index != -1:
        	#    index        
            left_res = self.binary_search(nums,target,left, index - 1)
            right_res =  self.binary_search(nums,target,index, right)
            #       
            if left_res > -1:
                return left_res
             #      
            if right_res > -1:
                return right_res
               #      
            return -1
        else:
        #           ，           
            return self.binary_search(nums,target,left,right)
        
    #    
    def binary_search(self,nums,target,left,right):
        
        if not nums:
            return -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid 
        return -1
        
        
    def binary_search_min_index(self,nums):

        if not nums:
            return -1
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = (left + right) // 2
            #       
            if mid >= 1 and nums[mid] < nums[mid - 1]:
                return mid

            if nums[mid] >= nums[right] and nums[mid] >= nums[left]:
                left = mid + 1
            else:
                right = mid - 1
        return -1