演算法

1// T(n) = T(n/2) + O(1)
2function binarySearch(a: number[], t: number, lo = 0, hi = a.length - 1): number {
3  if (lo > hi) return -1;
4  const mid = (lo + hi) >> 1;
5  if (a[mid] === t) return mid;
6  return a[mid] < t
7    ? binarySearch(a, t, mid + 1, hi)
8    : binarySearch(a, t, lo, mid - 1);
9}
10 
11// T(n) = 2T(n/2) + O(n)
12function mergeSort(a: number[]): number[] {
13  if (a.length <= 1) return a;
14  const mid = a.length >> 1;
15  const left = mergeSort(a.slice(0, mid));
16  const right = mergeSort(a.slice(mid));
17  const out: number[] = [];
18  let i = 0, j = 0;
19  while (i < left.length && j < right.length) {
20    out.push(left[i] <= right[j] ? left[i++] : right[j++]);
21  }
22  return out.concat(left.slice(i), right.slice(j));
23}
24 
25// T(n) = 3T(n/2) + O(n): three half-size products instead of four
26function karatsuba(x: number, y: number): number {
27  if (x < 10 || y < 10) return x * y;
28  const m = Math.floor(Math.max(String(x).length, String(y).length) / 2);
29  const p = 10 ** m;
30  const a = Math.floor(x / p), b = x % p;
31  const c = Math.floor(y / p), d = y % p;
32  const ac = karatsuba(a, c);
33  const bd = karatsuba(b, d);
34  const mid = karatsuba(a + b, c + d) - ac - bd;
35  return ac * p * p + mid * p + bd;
36}