Function Bisect

cpp/src/arrow/chunk_resolver.h:263–282

  }

  static inline int32_t Bisect(uint64_t index, const uint64_t* offsets, uint32_t lo,
                               uint32_t hi) {
    // Similar to std::upper_bound(), but slightly different as our offsets
    // array always starts with 0.
    auto n = hi - lo;
    // First iteration does not need to check for n > 1
    // (lo < hi is guaranteed by the precondition).
    assert(n > 1 && "lo < hi is a precondition of Bisect");
    do {
      const uint32_t m = n >> 1;
      const uint32_t mid = lo + m;
      if (index >= offsets[mid]) {
        lo = mid;
        n -= m;
      } else {
        n = m;
      }
    } while (n > 1);
    return lo;
  }
};

// Explicitly instantiate template base struct, for DLL linking on Windows