static int binarySearchNonRootIndex(Cell key, ByteBuff nonRootIndex,
      CellComparator comparator) {

      int numEntries = nonRootIndex.getIntAfterPosition(0);
      int low = 0;
      int high = numEntries - 1;
      int mid = 0;

      // Entries start after the number of entries and the secondary index.
      // The secondary index takes numEntries + 1 ints.
      int entriesOffset = Bytes.SIZEOF_INT * (numEntries + 2);

      // If we imagine that keys[-1] = -Infinity and
      // keys[numEntries] = Infinity, then we are maintaining an invariant that
      // keys[low - 1] < key < keys[high + 1] while narrowing down the range.
      ByteBufferKeyOnlyKeyValue nonRootIndexkeyOnlyKV = new ByteBufferKeyOnlyKeyValue();
      ObjectIntPair<ByteBuffer> pair = new ObjectIntPair<>();
      while (low <= high) {
        mid = low + ((high - low) >> 1);

        // Midkey's offset relative to the end of secondary index
        int midKeyRelOffset = nonRootIndex.getIntAfterPosition(Bytes.SIZEOF_INT * (mid + 1));

        // The offset of the middle key in the blockIndex buffer
        int midKeyOffset = entriesOffset // Skip secondary index
          + midKeyRelOffset // Skip all entries until mid
          + SECONDARY_INDEX_ENTRY_OVERHEAD; // Skip offset and on-disk-size

        // We subtract the two consecutive secondary index elements, which
        // gives us the size of the whole (offset, onDiskSize, key) tuple. We
        // then need to subtract the overhead of offset and onDiskSize.
        int midLength = nonRootIndex.getIntAfterPosition(Bytes.SIZEOF_INT * (mid + 2))
          - midKeyRelOffset - SECONDARY_INDEX_ENTRY_OVERHEAD;

        // we have to compare in this order, because the comparator order
        // has special logic when the 'left side' is a special key.
        // TODO make KeyOnlyKeyValue to be Buffer backed and avoid array() call. This has to be
        // done after HBASE-12224 & HBASE-12282
        // TODO avoid array call.
        nonRootIndex.asSubByteBuffer(midKeyOffset, midLength, pair);
        nonRootIndexkeyOnlyKV.setKey(pair.getFirst(), pair.getSecond(), midLength);
        int cmp = PrivateCellUtil.compareKeyIgnoresMvcc(comparator, key, nonRootIndexkeyOnlyKV);

        // key lives above the midpoint
        if (cmp > 0) low = mid + 1; // Maintain the invariant that keys[low - 1] < key
        // key lives below the midpoint
        else if (cmp < 0) high = mid - 1; // Maintain the invariant that key < keys[high + 1]
        else return mid; // exact match
      }

      // As per our invariant, keys[low - 1] < key < keys[high + 1], meaning
      // that low - 1 < high + 1 and (low - high) <= 1. As per the loop break
      // condition, low >= high + 1. Therefore, low = high + 1.

      if (low != high + 1) {
        throw new IllegalStateException(
          "Binary search broken: low=" + low + " " + "instead of " + (high + 1));
      }

      // OK, our invariant says that keys[low - 1] < key < keys[low]. We need to
      // return i such that keys[i] <= key < keys[i + 1]. Therefore i = low - 1.
      int i = low - 1;

      // Some extra validation on the result.
      if (i < -1 || i >= numEntries) {
        throw new IllegalStateException("Binary search broken: result is " + i
          + " but expected to be between -1 and (numEntries - 1) = " + (numEntries - 1));
      }

      return i;
    }
Performs a binary search over a non-root level index block. Utilizes the secondary index,
which records the offsets of (offset, onDiskSize, firstKey) tuples of all entries. the key we
are searching for offsets to individual entries in the blockIndex buffer the non-root index
block buffer, starting with the secondary index. The position is ignored.
@return the index i in [0, numEntries - 1] such that keys[i] <= key < keys[i + 1], if keys is
        the array of all keys being searched, or -1 otherwise
hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileBlockIndex.java