Binary Search

Does anyone remember when we had phone books and your grandma would ask for you to find Aunt Jemima's phone number? Well if you are new to computer science you probably didn't get that grand opportunity until today. But it is a interesting question to ask, how would you find anyone's phone number with a step by step process that was both fast and accurate? Well for starters you may go to each page and check but what if their name started with a 't'? That might take a lot thumb licks to get to the page that started with 't'.

Binary Search is a searching algorithm that splits the data in half and checks to see which side the value desired is on. It does this until a value is reached.

friends = [ Asheley: 1, David: 2, George: 3, Mary: 4, Nick: 5 ]

If i ask for Georges favorite number what will it return? Using binary search i can easily find this answer. Binary Search is dependent on a sorted array much like a phone book. Binary Search would then locate the middle of the array which in this case is George and immediately return 3. What if i asked for Mary's favorite number? Binary Search would find the middle and then check the other two halves. The left side contains Asheley, David and the right side contains Mary, Nick. Since M is not on the left side the left side gets thrown away and now we have an array of Mary and Nick. The algorithm will then check both names and eventually return 4.

I have illustrated binary search using code below. The function makes use of recursion and for those of you that are not familar with recursion I suggest you read my post on Recursion.

   // x is the term we want to find
   function binarySearch((array, left, right, x) => {
       if (right >= left) { 
         mid = left + (right - left)/2;
         
         // check to see if x is the middle
         if (array[mid] === x) return mid;
         
         // IF x is smaller than mid
         // then its on the left side
         else if (array[mid] > x) {
           return binarySearch(array, left, mid-1, x);
         }
         // x must be on right side
         else return binarySearch(array, mid+1, right, x)
       }
       // Element x is not in array
       else return -1;
   });
   ```