অ্যারেতে সর্বোচ্চ মান সম্পন্ন এলিমেন্টের ইনডেক্স বের করা

মান লজিয়ে, 'TestArray' ক্লাসে একটি প্রাইভেট অ্যারে এবং দুটি পাবলিক মেথড length() ও compare() রয়েছে। compare(l, r, x, y) দুটি সাবঅ্যারের সমSpielbericht করে:

যদি sum(array[l..r]) > sum(array[x..y]) → 1 রিটার্ন
যদি সমান হয় → 0 রিটার্ন
যদি কম হয় → -1 রিটার্ন

অ্যারে এক্সেস না করেই compare() ব্যবহার করে সর্বোচ্চ এলিমেন্টের ইনডেক্স বের করতে হবে।

ইনপুট: array = [8, 4, 2, 12, 11, 8, 4, 2, 7] → আউটপুট: 3। সর্বোচ্চ মান 12 ইনডেক্স 3-এ অবস্থিত।

সমাধানের ধাপসমূহ (বাইনারি সার্চ পদ্ধতি)

n := length()
low := 0, high := n - 1
যখন low < high:
- mid := floor((low + high + 1) / 2)
- যদি (low + high + 1) সম হয়:
  - res := compare(low, mid-1, mid, high)
  - যদি res == 1: high = mid - 1
  - অন্যথায়: low = mid
- অন্যথায় (বিষম):
  - res := compare(low, mid-1, mid+1, high)
  - যদি res == 1: high = mid - 1
  - যদি res == -1: low = mid + 1
  - অন্যথায়: return mid
যদি high == low: return high
return -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(self.__arr[l:r+1])
        val2 = sum(self.__arr[x:y+1])
        if val1 > val2: return 1
        elif val1 == val2: return 0
        else: 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]