⚡Flashcard Drill➔
NeetCode #269LC-1533MediumBinary SearchNC Algo100
← Back to All Problems

#269 · #1533 · Find the Index of the Large Integer(找出数组中的大整数下标)

📌 Problem Statement & Constraints

This is an interactive problem. An array of n integers has one element strictly larger than all others. ArrayReader.compareSub(l1, r1, l2, r2) compares the sums of two equal-length subarrays, returning 1, 0 or -1. Return the index of the largest element. Constraints: 2 <= n <= 5 * 10^4; at most 20 calls to compareSub.

💡 Core Algorithmic Approaches

  1. The array length doubles or halves each step, so the search space is halved by comparing two equal halves.
  2. If the length is even, split into two equal halves and compare them: the larger sum's half contains the maximum.
  3. If the length is odd, leave the middle element out and compare the two remaining halves. A tie means the middle element is the answer; otherwise the winning half contains it.
  4. Each step halves the range, so at most log2(50000) ≈ 16 calls are needed.

💻 Benchmark Python3 Implementation

class Solution:
    def getIndex(self, reader: "ArrayReader") -> int:
        n = reader.length()
        lo, hi = 0, n - 1
        while lo < hi:
            length = hi - lo + 1
            mid = (lo + hi) // 2
            if length % 2 == 0:
                # two equal halves: [lo, mid] and [mid+1, hi]
                c = reader.compareSub(lo, mid, mid + 1, hi)
                if c == 1:
                    hi = mid
                else:
                    lo = mid + 1
            else:
                # leave the middle element out
                c = reader.compareSub(lo, mid - 1, mid + 1, hi)
                if c == 0:
                    return mid         # the middle is the largest
                if c == 1:
                    hi = mid - 1
                else:
                    lo = mid + 1
        return lo

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n) calls to compareSub: about 16 for the maximum n.
💾 Space Complexity
O(1): a few indices.

⚠️ Interview Pitfalls & Follow-ups

  • Not excluding the middle element in the odd-length case: including it in one half biases the comparison and can hide the answer.
  • Treating a tie in the odd case as "the left half wins": a tie means the two halves are equal, so the excluded middle element must be the maximum.
  • Comparing unequal-length subarrays: the API requires equal lengths.
  • Binary searching by value: the array is not sorted, so only sum comparisons are available.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems