Logo

Programming-Idioms

History of Idiom 124 > diff from v26 to v27

Edit summary for version 27 by 1.7.4:
New JS implementation by user [1.7.4]
↷

Version 26

2018-12-28, 10:42:15

Version 27

2019-01-24, 11:42:36

Idiom #124 Binary search for a value in sorted array

Write function binarySearch which returns the index of an element having value x in sorted array a, or -1 if no such element.

Idiom #124 Binary search for a value in sorted array

Write function binarySearch which returns the index of an element having value x in sorted array a, or -1 if no such element.

Extra Keywords
dichotomic dichotomy
Extra Keywords
dichotomic dichotomy
Code 
function binarySearch(a, x, i = 0) {
  if (a.length === 0) return -1
  const half = (a.length / 2) | 0
  return (a[half] === x) ?
    i + half :
    (a[half] > x) ?
    binarySearch(a.slice(0, half), x, i) :
    binarySearch(a.slice(half + 1), x, half + i + 1)
}
Comments bubble
x | 0 removes the bit of x after the decimal.