< 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.