Pythonで回転ソート配列IIを検索

配列が昇順でソートされているとします。それは、事前に私たちに知られていないいくつかのピボットで回転します。たとえば、配列が[0,0,1,2,2,5,6]のような場合、これは[2,5,6,0,0,1,2]になる可能性があります。検索するターゲット値があります。それが配列で見つかった場合はtrueを返し、そうでない場合はfalseを返します。したがって、配列が[2,5,6,0,0,1,2]のようで、ターゲットが0の場合、出力は0になります

手順を見てみましょう-

• 低：=0および高：=配列のサイズ
• 低い<高い
  • 中：=低+（高-低）/ 2
  • nums [mid] =targetの場合、trueを返します
  • nums [low] =nums[mid]およびnums[high-1]=nums [mid]の場合、
    • 低値を1増やし、高値を1減らし、次の反復に進みます
  • nums [low] <=nums [mid]の場合、
    • if target> =nums [low] and target＆miinus; nums [mid]、次にhigh：=mid、それ以外の場合はlow：=mid + 1
  • それ以外の場合
    • target <=nums[high-1]およびtarget>nums[mid]の場合、low：=mid + 1、それ以外の場合はhigh：=mid
• falseを返す

理解を深めるために、次の実装を見てみましょう-

例

class Solution(object):
   def search(self, nums, target):
      low = 0
      high = len(nums)
      while low<high:
         mid = low + (high-low)//2
         if nums[mid] == target:
            return True
         if nums[low] == nums[mid] and nums[high-1] == nums[mid]:
            low +=1
            high -=1
            continue
         if nums[low]<=nums[mid]:
            if target >=nums[low] and target <nums[mid]:
               high = mid
            else:
               low = mid+1
         else:
            if target<=nums[high-1] and target>nums[mid]:
               low = mid+1
            else:
               high = mid
      return False
ob1 = Solution()
print(ob1.search([2,5,6,0,0,1,2], 0))

入力

[2,5,6,0,0,1,2]
0

出力

True