A Simple Binary Search Algorithm

Question & Examples

Write a function called binarySearch which accepts a sorted array and a value and returns the index at which the value exists. Otherwise, return -1.

// Examples
binarySearch([1,2,3,4,5],2) // 1
binarySearch([1,2,3,4,5],3) // 2
binarySearch([1,2,3,4,5],5) // 4
binarySearch([1,2,3,4,5],6) // -1

My Solution

function binarySearch(arr, val) {
  if (!val) {
    return -1;
  }
  if (arr.length === 0) {
    return -1;
  }
  let pointer1 = 0;
  let pointer2 = arr.length - 1;
  while (pointer1 < pointer2) { 
    let midPointIndex = Math.floor((pointer2 + pointer1) / 2);
    if (arr[midPointIndex] === val) {
      return arr.indexOf(val);
    }
    if (arr[midPointIndex] > val) {
      pointer2 = pointer2 - midPointIndex;
    }
    if (arr[midPointIndex] < val) {
      pointer1 = pointer1 + midPointIndex;
    }
  }
  return -1;
}

This code produces some errors. For example...

binarySearch([1,2,3,4,5],5)
// Expected -1 to be 4, 'binarySearch([1,2,3,4,5],5) should be 4.'.
 
binarySearch([5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99], 95) should be 16.
// Expected -1 to be 16, 'binarySearch([5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99], 95) should be 16.'.

A Better Solution

function binarySearch(arr, elem) {
 
  if(arr.length === 0) {
    return -1
  }
  
  let start = 0;
  let end = arr.length - 1;
  let middle = Math.floor((start + end) / 2)
 
  while(arr[middle] !== elem && start <= end) {
    if(elem < arr[middle]) {
      end = middle - 1;
    } else {
      start = middle + 1
    }
    // I shoud've updated the "middle" value
    middle = Math.floor((start + end) / 2)
  }
  if(arr[middle] === elem) {
    return middle
  }
  return - 1
}

This solution conditions the while loop to be while(arr[middle] !== elem && start <= end) which makes the rest of the code much easier to write.

Go back to list