Pythonで最大の要素が配置されている配列内のインデックスを見つけるプログラム

他のクラスからアクセスできない配列と、2つのパブリックメンバー関数length（）およびcompare（）を含む「TestArray」というクラスが与えられたとします。関数length（）は配列の長さを返し、関数compare（）は配列のさまざまなサブ配列を比較する3つの異なる値を返します。この関数は、入力として4つの値l、r、x、yを取り、次のように機能します-

• if（array [l] + array [l + 1] + ...... + array [r-1] + array [r]）>（array [x] + array [x + 1] + .. .. ... + array [y1] + array [y]）; 1を返します

• if（array [l] + array [l + 1] + ...... + array [r-1] + array [r]）=（array [x] + array [x + 1] + .. .. ... + array [y1] + array [y]）; 0を返します

• if（array [l] + array [l + 1] + ...... + array [r-1] + array [r]）<（array [x] + array [x + 1] + .. .. ... + array [y1] + array [y]）; -1を返します

配列自体にアクセスせず、クラスのメンバー関数のみを使用して、配列内の最大要素のインデックスを見つける必要があります。

したがって、入力がarray =[8、4、2、12、11、8、4、2、7]のような場合、出力は3になります。配列の最大要素は12で、インデックスに配置されます。 3。

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

• n：=length（）

• 低：=0

• 高：=n-1

• 低<高、実行

  • mid：=（low + high + 1）/ 2

    のフロア値

  • （low + high + 1）mod 2が0と同じ場合、

    • res：=compare（low、mid-1、mid、high）

    • resが1と同じ場合、

      • 高：=中-1

    • それ以外の場合

      • 低：=中

  • それ以外の場合

    • res：=compare（low、mid-1、mid + 1、high）

    • resが1と同じ場合、

      • 高：=中-1

    • それ以外の場合、resが-1と同じ場合、

      • 低：=中-1

    • それ以外の場合

      • 途中で戻る

  • 高が低と同じである場合、

    • ハイに戻る

• -1を返す

例（Python）

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

class TestArray:
   def __init__(self, array) -> None:
      self.__arr = array

   def length(self):
      return len(self.__arr)

   def compare(self, l, r, x, y):
      val1 = sum(i for i in self.__arr[l:r+1])
      val2 = sum(j for j in self.__arr[x:y+1])
      if val1 > val2:
         return 1
      elif val1 == val2:
         return 0
      elif val1 < val2:
         return -1

def solve(reader):
   n = reader.length()
   low,high = 0,n - 1
   while low < high:
      mid = (low+high+1)//2
      if (low+high+1)%2 == 0:
         res = reader.compare(low,mid-1,mid,high)
         if res == 1:high = mid - 1
         else:low = mid
      else:
         res = reader.compare(low,mid-1,mid+1,high)
         if res == 1:high = mid - 1
         elif res == -1:low = mid + 1
         else: return mid
      if high == low: return high
   return -1

arr_ob = TestArray([8, 4, 2, 12, 11, 8, 4, 2, 7])
print(solve(arr_ob))

入力

[8, 4, 2, 12, 11, 8, 4, 2, 7]

出力

3