freeCodeCamp Challenge Guide: Implement Binary Search

Implement Binary Search


Relevant Links


Hints

Hint 1

Sometimes it just helps to visualize what you are trying to do.

image credit: Binary Search - GeeksforGeeks

Hint 2

Tracking the location of the Left and Right values will let you control where you want search within an array. For your first search Left will be the beginning of an array and Right will be the end. If the first search doesn’t find the target value, you must search left or right of the middle value, depending on if the middle value is lesser or greater than the target value. So if you have to go left, Left is still the beginning of the array but Right now becomes the Middle value - 1 (you subtract because you already looked at the middle value!).

right = middle - 1;

Solutions

Solution 1 (Click to Show/Hide)
let binarySearch = (searchList, value) => {
  let arrayPath = [];

  //set initial L - M - R
  let left = 0;
  let right = searchList.length - 1;
  let middle = Math.floor(right / 2);

  //if first comparison finds value
  if (searchList[middle] == value) {
    arrayPath.push(searchList[middle]);
    return arrayPath;
  }

  while (searchList[middle] !== value) {
    //add to output array
    arrayPath.push(searchList[middle]);

    //not found
    if (right < left) {
      return 'Value Not Found';
    }
    // value is in left or right portion of array
    // update L - M - R
    if (searchList[middle] > value) {
      right = middle - 1;
      middle = left + Math.floor((right - left) / 2);
    } else {
      left = middle + 1;
      middle = left + Math.floor((right - left) / 2);
    }

    //if found update output array and exit
    if (searchList[middle] == value) {
      arrayPath.push(searchList[middle]);

      break;
    }
  }
  return arrayPath;
};
1 Like

Here is also my version that uses recursion:

function binarySearch(searchList, value, left=0, right=searchList.length-1, path=[]) {
  let mid = Math.floor((left+right)/2);
  path.push(searchList[mid]);
  if(searchList[mid] == value){
    return path;
  }
  if(left>=right){
    return "Value Not Found";
  }
  if(searchList[mid] > value){
    return binarySearch(searchList, value, left, mid-1, path);
  }
  return binarySearch(searchList, value, mid+1, right, path);
}

2 Likes