< Back 1533. Find the Index of the Large Integer We're given an object called reader that implements an API with length() and compareSub() methods. There's an black-box array where all the integers are the same, except for one integer that is larger than the rest. This integer is guaranteed to exist. length() returns the length of the black-box array. compareSub() takes indices for two different subarrays, and returns if they're equal, or unequal. Using this information, we binary search through the array, selecting two halves to compare. If they're equal, we know the larger integer is in the extra slice not contained in the two halves. If the right half is larger, we move the left pointer to the right half. If the left half is larger, we move the right pointer to the left half. We continue this process until we find the index of the larger integer. The solution is as follows: class Solution(object): def getIndex(self, reader): l = 0 length = reader.length() while length > 1: length //= 2 cmp = reader.compareSub( l, l + length - 1, l + length, l + length + length - 1 ) if cmp == 0: return l + length + length if cmp < 0: l += length return l _ Time Complexity: O(log(n)) - Where n is the length of the black-box array. _ Space Complexity: O(1) - Binary search requires constant space.