freeCodeCamp Challenge Guide: Implement Binary Search

Contributors
1

Implement Binary Search

Relevant Links

Hints

Hint 1

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

Binary-Search
Binary-Search1600×891 170 KB

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) 
function binarySearch(searchList, value) {
  const arrayPath = [];

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

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

    // check for value 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);
    }
  }

  // add target value to output array  
  arrayPath.push(searchList[middle]);

  return arrayPath;
}
5 Likes
2

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);
}
6 Likes