loading...

CodeRust - Binary Search

snesjhon profile image Jhon Paredes ・2 min read

Here's a series of posts of me going through each of the CodeRust tutorials in an effort to teach myself basic algorithms.

Progress So Far

I'm slowly, but surely, improving in my algorithm skills. Not a small feat as I don't have a proper CS background. But taking it 1-2 hours a day seems to be working.

I don't think I'll get to a comfortable point any time soon, but at least I'm working my way through it.

I realize that although going through each of these algorithms aren't going to help me in my every day at work, I know it'll help me in the long run. Thinking analytically is a strong skill that takes time.

Binary Search

Steps

  • At every step, consider the array between low and high indices
  • Calculate the mid index.
  • If element at the mid index is the key, return mid.
  • If element at mid is greater than the key, then reduce the array size such that high becomes mid - 1. Index at low remains the same.
  • If element at mid is less than the key, then reduce the array size such that low becomes mid + 1. Index at high remains the same.
  • When low is greater than high, key doesn't exist. Return -1.

Why the While loop

Because we need to iterate through whatever the size of the array is going to be we return -1 if low > high because that means we've gone through all of the halves of the array and we haven't found what we needed.

var arr = [0,1,2,4,5,6,7];
           L     M     H
           L  M  H 
                 L  M  H  
                  L M H  

Calculating Mid

Because mid is an ever shrinking array, we need to make sure that mid to also shift depending on the size of the array

This is done by adding low to the difference between high - low divided by 2.

// Given array, find the index of 4
var arr = [0,1,2,3,4,5,6,7,8];
var key = 4;
function binarySearch(arr, key){
  var low = 0;
   var high = arr.length - 1;

   while(low <= high){
     var mid = low + Math.floor((high - low) / 2);
     if(arr[mid] == key) {
       return mid;
     }
     if(arr[mid] > key){
       high = mid - 1; 
     } else {
       low = mid + 1;
     }
   }
   return -1; 
 }

Posted on by:

snesjhon profile

Jhon Paredes

@snesjhon

Just a kid from Oakland walking around and believing in fairytales.

Discussion

markdown guide