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 Xorword W, printX: index I, S stepsorX: 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
9 3 7 1 5 pear apple fig 3 num 7 num 4 word fig
7: index 3, 2 steps 4: not found, 3 steps fig: index 1, 1 steps
10 Zed alpha 2 word alpha word Zed
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");
}