Chương trình tìm chỉ mục phần tử lớn nhất trong mảng ẩn trong Python

Giả sử ta được cho một lớp TestArray chứa mảng không thể truy cập bởi lớp khác và hai hàm public length() và compare(). Hàm length() trả về độ dài mảng, hàm compare() trả về ba giá trị so sánh các mảng con. Hàm nhận bốn giá trị l, r, x, y và hoạt động:

• Nếu tổng array[l..r] > array[x..y]: trả về 1
• Nếu tổng array[l..r] = array[x..y]: trả về 0
• Nếu tổng array[l..r] < array[x..y]: trả về -1

Ta phải tìm chỉ mục của phần tử lớn nhất trong mảng không truy cập trực tiếp mảng và chỉ dùng các hàm thành viên.

Ví dụ: array = [8, 4, 2, 12, 11, 8, 4, 2, 7], kết quả là 3. Phần tử lớn nhất là 12 tại chỉ mục 3.

Giải thuật

1. n := length()
2. low := 0, high := n - 1
3. While low < high:
   • mid := floor((low + high + 1) / 2)
   • Nếu (low + high + 1) % 2 == 0:
     • res := compare(low, mid-1, mid, high)
     • Nếu res == 1: high := mid - 1
     • Ngược lại: low := mid
   • Ngược lại:
     • res := compare(low, mid-1, mid+1, high)
     • Nếu res == 1: high := mid - 1
     • Ngược lại nếu res == -1: low := mid + 1
     • Ngược lại: trả về mid
4. Nếu high == low: trả về high
5. Trả về -1

Ví dụ (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))

Input

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

Output

3