Binary Search

#algorithms #computerscience

Binary Search is an algorithm that finds an item in a list by continuously comparing the middle list item with the item you are looking for. It then splits the list to the left if the middle is greater or to the right if the middle is smaller.
I have seen a lot of programs that implement this with arrays and numbers which is very useful but I wanted to create a version with an array of objects, which encase strings and numbers, that finds a certain entry based on the number.

Implementation

So to start making this, get an object, any will do but in case you are having a hard time thinking of one here is an example:

let names = [
  {"Adeline Garrett": 11},
  {"Carlene Stevenson": 24},
  {"Glen Moyer": 36},
  {"Tamara Vega": 47},
  {"Cecile Dixon": 54},
  {"Sebastian Burton": 69},
  {"Natasha Sloan": 75},
  {"Roger Crawford": 83},
  {"Damien Hensley": 93},
  {"Josie Frost": 103},
];

Now for the binary search, create a function that splits the array in half and gets the value from the midpoint. Since the array is already sorted this is pretty easy. Then implement recursion until the entry is found:


let binSearchObj = ( arr, numb) => {
    let midPoint = Math.floor(arr.length / 2); //get mid index
    let mid = Object.values(arr[midPoint])[0]; //get mid value
    if (mid > numb) {
        let newArr = arr.slice(0, midPoint); 
        //slice the array from the beginning to the midPoint 
        return binSearchObj(newArr, numb); 
        //recursively call the function again with the sliced 
        //array
    }
    if (mid < numb) {
        let newArr = arr.slice(midPoint, arr.length); 
        //slice the array from the midpoint to the end
        return binSearchObj(newArr, numb);
        //recursively call the function again with the sliced 
        //array
    return arr[midPoint];
    //if the function gets to this point then the only thing left 
    //is what you are looking for
}

console.log(binSearchObj(names, 103))

Try this out with some different arrays. The example above did not implement a check for non-existent search items yet, so I leave that to you to figure out how to do it. This is just a good start for a more robust binary search algorithm