C++で回転ソート配列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]の場合、

    • target> =nums[low]およびtarget

  • それ以外の場合

    • target <=nums[high-1]およびtarget>nums[mid]の場合、low：=mid + 1、それ以外の場合、high：=mid

  • falseを返す

例

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

class Solution(object):
   def search(self, nums, target):
      """
      :type nums: List[int]
      :type target: int
      :rtype: int
      """
      low = 0
      high = len(nums)
      while low<high:
         mid = low + (high-low)//2
         print(mid)
      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

入力

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

出力

true