Binary Search

An Algorithm is a set of instructions for solving a problem You can think of an algorithm like a recipe in a cookbook, which tells the reader the specific steps for preparing a meal. There are different types of algorithms. One of them is to search through an array, they are refferred to as searching algorithm. One of these searching algorithm is called Binary Search.

The main point of Binary Search is for finding an element's position in a sorted array. Binary Search tackles the problem with the divide and conquer approach. Meaning it would divide the problem to the smallest possibility to get the answer. The first step would be to have an array to perform the search.

Let try to find the value 4. We would need to set 2 pointers. One pointer would be called low and placed on the lowest position and the other would be called high and it would be for the highest position

We also need to find the middle element in our array. We can create a variable called mid and equal it to the sums of the lowest index and the highest index then the divide the sum by 2. This will give us the middle position of the array: arr[(low + high)/2] = 6

Now, we need to check if the value we are looking for is mid, less than mid, or more than mid. If it's equal to mid then we return mid. If the value we're looking for is greater then we replace low to low = mid + 1. Meaning that we are focusing on the indexs of the array after the mid index. If the value is less than mid, then we replace high to high = mid + 1, where we focuse on the elements before the middle position.

We will repeat these steps until low meets high or until our value is found

GREATTTTT!!!!!! 4 was found

Pseudocode:

do until the pointers low and high meet each other.
    mid = (low + high)/2
    if (x == arr[mid])
        return mid
    else if (x > arr[mid]) // x is on the right side
        low = mid + 1
    else                       // x is on the left side
        high = mid - 1

The code in JavaScript:

// Program to implement iterative Binary Search


// A iterative binary search function. It returns
// location of x in given array arr[low..high] is present,
// otherwise false

 function binarySearch(arr, x)
{   
    let low = 0;
    let high = arr.length - 1;
    let mid;
    while (high <= low) {
         mid = Math.floor((high - low) / 2);

        // If the element is present at the middle
        // itself
        if (arr[mid] == x)
            return mid;

        // If element is smaller than mid, then
        // it can only be present in left subarray
        if (arr[mid] > x)
            high = mid - 1;

        // Else the element can only be present
        // in right subarray
        else
            low = mid + 1;
    }

    // We reach here when element is not
    // present in array
    return false;
}