array-10e6x100-search.js

const count = 10e6
const length = 100

console.time('generate')
const chars = Array(52).fill().map((_, i) => String.fromCharCode(i < 26 ? i + 65 : i + 71))
const char = () => chars[Math.random() * chars.length | 0]
const triplets = chars.flatMap(a => chars.flatMap(b => chars.flatMap(c => [a, b, c].join(''))))
const triplet = () => triplets[Math.random() * triplets.length | 0]
const main = Array(Math.floor(length / 3)).fill(0)
const tail = Array(length - main.length * 3).fill(0)
const word = () => [main.map(triplet).join(''), tail.map(char).join('')].join('')
const pool = []
for (let i = 0; i < count; i++) pool.push(word())
console.timeEnd('generate')

console.time('sort')
pool.sort()
console.timeEnd('sort')

if (typeof process !== 'undefined') console.log(`${process.memoryUsage().rss / 2**20} MiB`)

const query = (q) => {
  let pos = count / 2 | 0, delta = count / 4, res
  while (res = q(pos)) {
    if (res < 0) pos -= delta | 0 || 1
    if (res > 0) pos += delta | 0 || 1
    if (pos < 0 || pos >= count) return null
    delta /= 2
  }
  return pos
}
const search = (prefix) => {
  console.time('search')
  const compare = (str) => (str < prefix) ? +1 : str.startsWith(prefix) ? 0 : -1
  const first = query((pos) => {
    const curr = compare(pool[pos])
    return (curr > 0 || pos === 0) ? curr : (compare(pool[pos - 1]) - 1)
  })
  const last = query((pos) => {
    const curr = compare(pool[pos])
    return (curr < 0 || pos + 1 === count) ? curr : (compare(pool[pos + 1]) + 1)
  })
  if (first === null || last === null) return 0
  console.timeEnd('search')
  return { first, last, count: last - first + 1 }
}

console.log(search('Tst'))