TypeScript: A generic binary search

Write binary search once, for any type, by passing in how to compare two values.

What to build

A program that searches sorted numbers and sorted words with the same generic function.

Requirements

  • Write binarySearch<T>(items: readonly T[], target: T, compare: (a: T, b: T) => number): [number, number] returning the index of target (or -1) and the number of steps.
  • Use the classic loop: lo = 0, hi = length - 1; while lo ≤ hi: mid = floor((lo + hi) / 2), one step; if equal, found; if the middle item is smaller, lo = mid + 1, else hi = mid - 1.
  • Sort the numbers in increasing order and the words in alphabetical order (with < and >, not localeCompare) before searching.
  • For each query num X or word W, print X: index I, S steps or X: not found, S steps.

Input

Line 1: numbers separated by spaces. Line 2: words separated by spaces. Line 3: q. Then q queries.

Output

q lines.

Constraints

1 to 1000 distinct numbers and 1 to 1000 distinct words; 1 ≤ q ≤ 50.

Example

Input:

9 3 7 1 5
pear apple fig
3
num 7
num 4
word fig

Output:

7: index 3, 2 steps
4: not found, 3 steps
fig: index 1, 1 steps

Why it works

The comparison function is the only part that depends on the type, so the search itself is written once, and the step counts show the logarithmic cost: about log₂(n) looks, whatever the type.

Examples

Example 1 · Input
9 3 7 1 5
pear apple fig
3
num 7
num 4
word fig
Expected output
7: index 3, 2 steps
4: not found, 3 steps
fig: index 1, 1 steps
Example 2 · Input
10
Zed alpha
2
word alpha
word Zed
Expected output
alpha: index 1, 2 steps
Zed: index 0, 1 steps

Hints

Hint 1

binarySearch<T>(items: readonly T[], target: T, compare: (a: T, b: T) => number) works for any type that can be compared.

Hint 2

Count one step each time the loop looks at a middle item.

Solution

Show one correct solution (try it yourself first)
const read = (): string => prompt() ?? "";

function binarySearch<T>(items: readonly T[], target: T, compare: (a: T, b: T) => number): [number, number] {
  let lo = 0;
  let hi = items.length - 1;
  let steps = 0;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    steps++;
    const c = compare(items[mid], target);
    if (c === 0) return [mid, steps];
    if (c < 0) lo = mid + 1;
    else hi = mid - 1;
  }
  return [-1, steps];
}

const byNumber = (a: number, b: number): number => a - b;
const byText = (a: string, b: string): number => (a < b ? -1 : a > b ? 1 : 0);

const numbers = read().split(" ").map(Number).sort(byNumber);
const words = read().split(" ").sort(byText);
const q = Number(read());
for (let i = 0; i < q; i++) {
  const [kind, value] = read().split(" ");
  const [index, steps] = kind === "num" ? binarySearch(numbers, Number(value), byNumber) : binarySearch(words, value, byText);
  console.log(value + ": " + (index >= 0 ? "index " + index : "not found") + ", " + steps + " steps");
}

Lesson: Generic functions →