Need suggestions to improve this binary search function

[gaac510]

I’m trying to recreate a binary search function I read somewhere but couldn’t remember all the details.

I think I got the basics of it but could anyone suggest potential improvements in terms of (from most to least important):

• Potential edge case failures
• Performance
• Code readability

Thanks!

/*
Function accepts five arguments:
> `arr`: source array to perform search; must contain only integers; must be in asscending or descending order.
> `target`: integer to look for.
> `isAsc`: optional boolean indicating whether source array is in asscending order; default is true.
> `start`: optional integer specifying the self-included starting index for the search; default is 0.
> `end`: optional integerspecifying the self-included ending index for the search; default is the last index of the source array.

Function returns either:
> An integer representing the index where target was found; or
> Undefined if target wasn't found.
Note if elements of the source array aren't distinct, a returned integer isn't guaranteed to correspond to a specific occurance of target.
*/

function binarySearch(arr, target, isAsc = true, start = 0, end = arr.length - 1) {
  // Deal with edge cases first:
  switch(true) {
    case end < start:
      return;
    case arr[start] === target:
      return start;
    case arr[end] === target:
      return end;
    case start + 1 === end:
      return;
  }
  // Where at least one element between start index and end index:
  let midIdx = ~~((start + end) / 2)
  switch(true) {
    case arr[midIdx] === target:
      return midIdx;
    case arr[midIdx] < target:
      return binarySearch(
        arr, 
        target,
        isAsc, 
        isAsc === false? start+1: midIdx+1, 
        isAsc === false? midIdx-1: end-1
      );
    case arr[midIdx] > target:
      return binarySearch(
        arr, 
        target,
        isAsc,
        isAsc === false? midIdx+1: start+1, 
        isAsc === false? end-1: midIdx-1
      );
  }
}

[JeremyLT]

@gaac510

switch(true)

Fwiw, I hate switch trues. They are not ideomatic.

You should be able to simplify this quite a bit

function findItBinary(arr, target, isAsc=true, start=0, stop=arr.length-1) {
  // Stop recursion 
  if (start === stop) return;
  // Compute midpoint
  const mid = Math.floor((start + stop)/2);
  // Check for element
  if (arr[mid] === target) return mid;
  // Recurse
  let [newStart, newStop] = [start, mid];
  if ((isAsc && arr[mid] > target) ||
      (!isAsc && arr[mid] < target))
    [newStart, newStop] = [mid, stop];
  return findItBinary(arr, target, isAsc, newStart, newStop);
}

Probably need to test for edge cases, but that should be close.

When calling the same function in multiple places, I find it tidier to build the list of arguments and call the function once.

Also, your edge checks were causing a lot of repetition, so I don’t know if it actually helped your performance. The old midpoint was always one of the new endpoints, and the other was an old endpoint, so you were checking things that cannot match. Might be worth adding a check at 0 and n-1 on the first call though.