JavaScript: Searching

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19function linearSearch(values, target) {
  for (let i = 0; i < values.length; i++) {
    if (values[i] === target) return i;
  }
  return -1;                       // same convention as indexOf
}

// A version taking a predicate, which is what findIndex does.
function searchBy(values, matches) {
  for (let i = 0; i < values.length; i++) if (matches(values[i], i)) return i;
  return -1;
}

const plates = ['LAG-441-XA', 'ABJ-772-KM', 'ENU-318-PH', 'ABJ-772-KM'];

console.log('found at    :', linearSearch(plates, 'ENU-318-PH'));
console.log('not present :', linearSearch(plates, 'KAN-905-BD'));
console.log('first of two:', linearSearch(plates, 'ABJ-772-KM'));
console.log('by predicate:', searchBy(plates, (p) => p.startsWith('ENU')));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44function binarySearch(sorted, target) {
  let low = 0;
  let high = sorted.length - 1;

  while (low <= high) {                 // <= , not < : the one-element range matters
    // Written this way out of habit: in languages with fixed-width ints,
    // (low + high) can overflow. It cannot here, but the habit is free.
    const mid = low + Math.floor((high - low) / 2);
    const value = sorted[mid];

    if (value === target) return mid;
    if (value < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

const sorted = [1, 3, 5, 7, 9, 11, 13];

for (const t of [1, 7, 13, 8]) {
  console.log('looking for', t, '->', binarySearch(sorted, t));
}

// The silent failure: unsorted input gives a wrong answer, not an error.
const unsorted = [9, 1, 7, 3];
console.log('binary search on unsorted:', binarySearch(unsorted, 7), '(7 is really at index 2)');

// Count the steps, to show the halving.
function steps(n) {
  const list = Array.from({ length: n }, (_, i) => i);
  let count = 0;
  let low = 0;
  let high = n - 1;
  while (low <= high) {
    count++;
    const mid = low + Math.floor((high - low) / 2);
    if (list[mid] === n - 1) break;
    if (list[mid] < n - 1) low = mid + 1;
    else high = mid - 1;
  }
  return count;
}

console.log('steps to find the last of 1000:', steps(1000));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34// Leftmost: inserts before any equal values.
function lowerBound(sorted, target) {
  let low = 0;
  let high = sorted.length;          // note: length, not length - 1
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (sorted[mid] < target) low = mid + 1;
    else high = mid;
  }
  return low;
}

// Rightmost: inserts after any equal values.
function upperBound(sorted, target) {
  let low = 0;
  let high = sorted.length;
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (sorted[mid] <= target) low = mid + 1;   // <= is the only change
    else high = mid;
  }
  return low;
}

const sorted = [1, 3, 3, 3, 7, 9];

console.log('lowerBound(3):', lowerBound(sorted, 3));
console.log('upperBound(3):', upperBound(sorted, 3));
console.log('how many 3s  :', upperBound(sorted, 3) - lowerBound(sorted, 3));

// Inserting keeps the order.
const inserted = [...sorted];
inserted.splice(lowerBound(inserted, 5), 0, 5);
console.log('after inserting 5:', inserted);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19const buses = [
  { plate: 'LAG-441-XA', route: 'Lagos - Abuja', seats: 14 },
  { plate: 'ABJ-772-KM', route: 'Lagos - Kano', seats: 30 },
  { plate: 'ENU-318-PH', route: 'Lagos - Abuja', seats: 7 },
];

// One-off lookup.
const findByPlate = (plate) => buses.find((b) => b.plate === plate) ?? null;

// Repeated lookups: pay the O(n) once, then every lookup is O(1).
const index = new Map(buses.map((b) => [b.plate, b]));
const lookup = (plate) => index.get(plate) ?? null;

// All matches, not just the first.
const onRoute = (route) => buses.filter((b) => b.route === route);

console.log('found      :', findByPlate('ABJ-772-KM'));
console.log('missing    :', findByPlate('KAN-905-BD'));
console.log('two on the Abuja run:', onRoute('Lagos - Abuja').map((b) => b.plate));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27function findPeak(values) {
  if (values.length === 0) return -1;

  let low = 0;
  let high = values.length - 1;

  // low < high, so mid + 1 is always in range.
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (values[mid] < values[mid + 1]) low = mid + 1;   // still climbing
    else high = mid;                                     // at or past the peak
  }
  return low;
}

const linearPeak = (values) => values.indexOf(Math.max(...values));

const cases = [
  [1, 3, 7, 12, 9, 4],
  [1, 2, 3, 4],          // rises the whole way: peak is last
  [9, 5, 2],             // falls the whole way: peak is first
  [42],
];

for (const c of cases) {
  console.log(JSON.stringify(c).padEnd(20), 'peak at', findPeak(c), '=', c[findPeak(c)]);
}