Cacher is the code snippet organizer for pro developers

We need to understand the basics of logarithms because one of the most common and fastest search algorithms, the so-called “Binary Search” , has an efficiency of O(logN).

For most search requirements, Binary Search is the most efficient method possible.

First, I’ll explain what a Binary Search is, and then we can see how it is relevant to logarithms.

Let’s start with an array of numbers, from 1 to 15. For now, we’ll assume their already sorted from the smallest to the biggest.

let array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Now let’s say we want the computer to find the number 11.

A brute-force method to achieve this would have an efficiency of O(N), and might look something like this:

function findEleven(array){
  for (let i = 0; i < array.length; i++){
    if (array[i] === 11) {
      return i;
    } 
  }
}

But we can do better! Here are the steps that the Binary Search method would take:

Stage 1 The Binary Search method involves finding the mid-point of the array, which in this case is the number 8. 11 is higher than 8. That means we can cut the array in half, ignoring the numbers 1–7 and create a second array with the numbers 9–15.

Stage 2 Let’s find the mid-point of our new array: that gives us the number 12. 11 is lower than 12. So we can cut our second array in half, ignoring 13–15, and create a third array with the numbers 9–11.

Stage 3 Finally, we’ll cut the third array in half, giving us the number 10. 11 is higher than 10, and as it happens only one number is higher than 10: we’ve found it!

For an array of this size, the maximum number of steps to the solution is 3. Compare that with the O(N) function. The maximum number steps it could take is 15.

If you double the data going into the Binary Search function, you get only 1 more step. But if you double the data going into the O(N) function, you get a potential 15 more steps!

Here’s what Binary Search might look like in JavaScript.

We’ll define a function that takes two parameters: an array of numbers (which must be sorted), and a search-value that we’re looking for.

function binarySearch(array, searchValue) {

  // Define start, end and pivot (middle)
  let start = 0;
  let end = array.length - 1;
  let pivot = Math.floor((start + end) / 2);
  
  // As long as the pivot is not our searchValue and the array is greater than 1, 
  // define a new start or end.
  while (array[pivot] !== searchValue && start < end) {
    if (searchValue < array[pivot]) {
      end = pivot - 1
    } else {
      start = pivot + 1
    }
    // Every time, calculate a new pivot value
    pivot = Math.floor((start + end) / 2);
  };
  
  // If the current pivot is out search value, return it's index. 
  // Otherwise, return false.
  return array[pivot] === searchValue ? pivot : false;
};