在 Python 中编写程序以查找数组中最大元素所在位置的索引

假设我们有一个名为 ‘TestArray’ 的类，它包含一个其他类无法访问的数组和两个公共成员函数 length() 和 compare()。函数 length() 返回数组的长度，函数 compare() 比较来自数组的各种子数组的三个不同值，并返回结果。该函数接受 l，r，x，y 四个值作为输入，工作方式如下 −

如果 (array[l] + array[l+1]+……+array[r-1]+array[r]) > (array[x] + array[x+1]+……+array[y1]+array[y]); 则返回 1
如果 (array[l] + array[l+1]+……+array[r-1]+array[r]) = (array[x] + array[x+1]+……+array[y1]+array[y]); 则返回 0
如果 (array[l] + array[l+1]+……+array[r-1]+array[r]) < (array[x] + array[x+1]+……+array[y1]+array[y]); 则返回 -1

我们必须在不访问数组本身并仅使用类的成员函数的情况下找到数组中最大元素的索引。

因此，我们将执行以下步骤 −

n := length()
low:= 0
high := n – 1
while low < high, do
- mid := (low+high+1) / 2 的 floor 值
- 如果 (low+high+1) mod 2 相同，则
  - res := compare(low, mid-1, mid, high)
  - 如果 res 相同，则
  - high := mid -1
  - 否则，
  - low := mid
- 否则，
  - res := compare(low, mid-1, mid+1, high)
  - 如果 res 相同，则
  - high := mid -1
  - 如果 res 是 -1，则
  - low := mid -1
  - 否则，
  - return mid
- 如果 high 与 low 相同，则
  - return high
返回 -1

更多Python相关文章，请阅读：Python 教程

示例（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))