The Binary Search Algorithm

If we are given random array and search for a given element !!

Simple Approach : traversing the array once.

Little modification : Now what if we are given an sorted array , now how can one find the element !!

Simple Approach : Linear search i.e. again by traversing the array elements one by one.

// to check whethear element present or not
bool find_element(int A[],int length,int elem_to_found)
{
    bool ans = false; // assume not found till now
    for(int i=0;i<length;i++)
        if(A[i]==elem_to_found)
            ans = true; // element found

    return ans;
}

Task : Think what should we have to do in order to find at which index element find in array

Now, think what is use of sorting for searching a element.

Here comes best tool binary search i.e. you dont have to traverse a whole array for searching the element and
here how it works :

Binary search looks for a element_to_be_found by comparing the middle index of array (mid)
If its less than the element_to_be_found then it search in the right half of the array i.e. (from mid till end of array)
otherwise if its greater than element_to_be_found than it searches in the left half i.e. (from 0 till mid of array)

Lets look at the implementation of binary search first move to recursive function :

// lets look at the base cases first ( most imp for recursive function )
// if element_to_be_found is found return
// if low(left) and high(right) goes out of bound then return

binary_search_recur(int A[],int element_to_be_found,int low,int high)
{
    // element_to_be_found not present in the array
    if(low>high)    return -1;

    int mid = (low+high)/2;
    // element found at mid position
    if(A[mid]==element_to_be_found)    return mid;

    // if its greater than the mid element recurse again for left half of array i.e. (low,mid-1)
    if(element_to_be_found>A[mid])
        binary_search_recur(A,element_to_be_found,low,mid-1)

    // else its less than the mid element recurse again for right half of array i.e. (mid+1,high)
    else(element_to_be_found>A[mid])
        binary_search_recur(A,element_to_be_found,mid+1,high)
}

Now look at the iterative one : ;)

binary_search(int A[],int element_to_be_found)
{
    int low = 0, high = size(A);

    // search for the whole array

    while(low<=high)
    {
        // find the middle value
        mid = (low+high)/2;

        // if middle element eequals element_to_be_found return index
        if(element_to_be_found==A[mid])
            return mid;
        // if its less then the middle element then it searches for right half and leave the left half
        else if(element_to_be_found<A[mid])
            low = mid+1;
        // if its greater then the middle element then it searches for left half and leave the right half
        else
            high = mid-1;
    }
    // target not found
}

// seems easy ;)
// we can make fun with binary search with structures, trees, reverse binary search