Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonで回転した並べ替えられた配列を検索する

配列が昇順で並べ替えられており、事前に不明なピボットで回転していると考えてください。たとえば、[0,1,2,4,5,6,7]は[4,5,6,7,0,1,2]になります。検索にターゲット値を指定しました。配列で取得できる場合はそのインデックスを返し、そうでない場合は-1を返します。配列に重複が存在しないと想定できます。したがって、配列が[4,5,6,7,0,1,2]のような場合、この要素のインデックスはインデックス4に存在するため、出力は4になります。

これを解決するには、次の手順に従います-

  • 低：=0および高：=配列の長さ
  • 低い<高い
    • midをmidとして見つける：=low +（high-low）/ 2
    • arr [mid] =targetの場合、midに戻ります
    • if arr [low] <=arr [mid]
      • target> =arr[low]およびtarget
    • それ以外の場合
      • target <=arr[high-1]およびtarget>arr[mid]の場合、low：=mid + 1、それ以外の場合はhigh：=mid
  • 戻り値-1
例（Python）

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

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 mid
         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 -1
ob1 = Solution()
print(ob1.search([4,5,6,7,8,0,1,2], 0))

入力

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

出力

5

  1. Pythonプログラムでの挿入ソート

    この記事では、Python3.xでの挿入ソートの実装について学習します。またはそれ以前。 アルゴリズム ソートされた配列を各反復で拡張することにより、入力要素を反復します。 現在の要素を、並べ替えられた配列で使用可能な最大値と比較します。 現在の要素の方が大きい場合は、その要素をそのままにして次の要素に移動します。それ以外の場合は、並べ替えられた配列内で正しい位置を見つけて、配列内のその位置に移動します。 これは、並べ替えられた配列内の現在の要素よりも大きいすべての要素を右にシフトすることで実現されます。 それでは、アルゴリズムの視覚的表現を見てみましょう

  2. 挿入ソート用のPythonプログラム

    この記事では、Python3.xでの挿入ソートの実装について学習します。またはそれ以前。 アルゴリズム 1. Iterate over the input elements by growing the sorted array at each iteration. 2. Compare the current element with the largest value available in the sorted array. 3. If the current element is greater, then it leaves the element in its place &n