Logo

Programming-Idioms

History of Idiom 124 > diff from v27 to v28

Edit summary for version 28 by 1.7.4:
[JS] *whine whine*
↷

Version 27

2019-01-24, 11:42:36

Version 28

2019-01-24, 11:44:02

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)
}
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.
Comments bubble
x | 0 removes the bit of x after the decimal.
This would be easier if JavaScript had more builtins for list processing.