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
- The array length doubles or halves each step, so the search space is halved by comparing two equal halves.
- If the length is even, split into two equal halves and compare them: the larger sum's half contains the maximum.
- 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.
- Each step halves the range, so at most
log2(50000) ≈ 16calls 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.