Binary Search

Find a value in a sorted list by halving the search range at every step — O(log n).

Version 1.0.0 Versions: 1.5.0 1.4.0 1.3.0 1.2.0 1.1.0 1.0.0

This is an older version. The current version is 1.5.0.

Implementations

JavaScript can be viewed here but not run in Zerethon IDE yet.

Files

binary_search.js entry

// Zerethon Official Sample: binary-search 1.0.0 (view only — the IDE cannot run JavaScript yet).
// a must be sorted ascending. Returns the index of target, or -1.
function binarySearch(a, target) {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (a[mid] === target) return mid;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

const numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
for (const target of [23, 2, 91, 7]) {
  const index = binarySearch(numbers, target);
  console.log(`search ${target}: ${index === -1 ? 'not found' : `found at index ${index}`}`);
}

Source: Zerethon Official Sample. Algorithm as shown in the Zerethon Tools Binary Search Visualizer.