Binary search in javascript

Introduction

Binary search is used to find an element in an array. It is useful when you have data in sorted order. Generally data in ascending order is preferred but you can change your code little to make it work for descending work too.

e.g - let’s say you are creating an application to store contacts. In contacts you are storing name, email & mobile no. You are showing the users the contact name by ascending order i.e- name which starts with a are being shown first & name which starts with z are in last.

Now you want to search a contact having name “ujjwal”. In this case if we will do a linear search then we will have to visit every element & since “ujjwal” is a value which will be in last , so it will take much more time

but if we will do a binary search then it will be faster since it doesn’t visit every element.

Binary search is divide & conquer algorithm. In this algorithm- we find the middle position of array ,then compare it with search value & this helps to find the near location of search value.

Let’s write the program for binary search.

Let’s Code

function binarySearch(arr, value) {
    var beg = 0;
    var end = arr.length;
    var getMid = function() {
        return parseInt((beg + end) / 2);
    }
    var mid = getMid();
    while (beg <= end && value != arr[mid]) {
        if (value > arr[mid]) { // value is right of middle
            beg = mid + 1;
        } else { // value is left of middle
            end = mid - 1;
        }
        mid = getMid();
    }
    if (arr[mid] == value) {
        console.log("value found");
    } else {
        console.log("value not found");
    }
}
binarySearch([1, 2, 5, 9], 2);

In this program -

• We first find the begining, end & middle position of the array.
• We do a loop until the value is found or (beg>end).
• Inside the loop - we compare search value with value at mid & if it is greater which means value is right of middle element so we update the beginning position & if it is less which means value is left of middle element so we update the end position.
• We update the mid value at every iteration.
• In the last if value is present at mid then we print value is found other not found.

if you are finding this difficult, just write the program & try to debug at line where you are finding it difficult.

Thanks for reading it guys. Hope you find it useful!.