একটি অ্যারেতে সূচক খুঁজে বের করার প্রোগ্রাম যেখানে পাইথনে সবচেয়ে বড় উপাদানটি অবস্থিত

ধরুন, আমাদেরকে 'TestArray' নামক একটি ক্লাস দেওয়া হয়েছে যাতে এমন একটি অ্যারে রয়েছে যা অন্যান্য ক্লাসের দ্বারা অ্যাক্সেসযোগ্য নয় এবং দুটি পাবলিক সদস্য ফাংশন length() এবং compare()। ফাংশন length() অ্যারের দৈর্ঘ্য প্রদান করে এবং ফাংশন compare() অ্যারে থেকে বিভিন্ন সাবয়ারের তুলনা করে তিনটি ভিন্ন মান প্রদান করে। ফাংশনটি ইনপুট হিসাবে চারটি মান l, r, x, y নেয় এবং এইভাবে কাজ করে −

• যদি (অ্যারে[l] + অ্যারে[l+1]+......অ্যারে[r-1]+অ্যারে[r])> (অ্যারে[x] + অ্যারে[x+1]+... ... অ্যারে[y1]+অ্যারে[y]); এটি 1

  প্রদান করে

• যদি (অ্যারে[l] + অ্যারে[l+1]+......অ্যারে[r-1]+অ্যারে[r]) =(অ্যারে[x] + অ্যারে[x+1]+... ... অ্যারে[y1]+অ্যারে[y]); এটি 0

  প্রদান করে

• যদি (অ্যারে[l] + অ্যারে[l+1]+...... অ্যারে[r-1]+অ্যারে[r]) <(অ্যারে[x] + অ্যারে[x+1]+... ... অ্যারে[y1]+অ্যারে[y]); এটি ফেরত দেয় -1

আমাদের অ্যারের সর্বোচ্চ উপাদানের সূচী খুঁজে বের করতে হবে অ্যারেটি অ্যাক্সেস না করে এবং শুধুমাত্র ক্লাসের সদস্য ফাংশন ব্যবহার না করে।

সুতরাং, যদি ইনপুটটি অ্যারের মত হয় =[8, 4, 2, 12, 11, 8, 4, 2, 7], তাহলে আউটপুট হবে 3। অ্যারের সবচেয়ে বড় উপাদান হল 12 এবং এটি সূচকে অবস্থিত। 3.

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=দৈর্ঘ্য()

• কম:=0

• উচ্চ :=n - 1

• যখন কম <উচ্চ, করুন

  • মধ্য :=(নিম্ন+উচ্চ+1) / 2

    এর তল মান

  • যদি (নিম্ন+উচ্চ+1) মোড 2 0 এর মত হয়, তাহলে

    • res :=তুলনা করুন (নিম্ন, মধ্য-1, মধ্য, উচ্চ)

    • যদি রেস 1 এর মত হয়, তাহলে

      • উচ্চ :=মধ্য -1

    • অন্যথায়,

      • নিম্ন :=মধ্য

  • অন্যথায়,

    • res :=তুলনা (নিম্ন, মধ্য-1, মধ্য+1, উচ্চ)

    • যদি রেস 1 এর মত হয়, তাহলে

      • উচ্চ :=মধ্য -1

    • অন্যথায় যখন res-এর সমান হয় -1, তখন

      • নিম্ন :=মধ্য -1

    • অন্যথায়,

      • মাঝামাঝি ফেরত

  • উচ্চ যদি নিম্নের সমান, তাহলে

    • উচ্চ রিটার্ন

• রিটার্ন -1

উদাহরণ (পাইথন)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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