Searching algorithms - Binary Search

Binary Search is a Divide and Conquer algorithm. In Divide and Conquer, we reduce a larger problem into smaller subproblems recursively until the problem is small enough that the solution is trivial.

A important condition for Binary Search is that the array should be a sorted array. If the array is sorted in ascending order, Binary Search compares the target element with the middle element of the array. If the target element matches, then it returns true. Otherwise, if the target is less than the middle element then it will recurse on the sub-array to the left of the middle element or if the item is greater then it will recurse on the sub-array to the right of the middle element. So, at each step the size of array will be reduced to half. After repeating this recursion, it will eventually be left with a single element.

Pseudo code or binary search:

Algorithm BinarySearch(Array, left, right, target) 
{
    if left is less than or equal to right then :
        mid = (left + right) / 2
        if Array[mid] is equal to target
            return true
        else if item is less than Array[mid] 
            recurse on the left subarray
        else if item is greater than Array[mid] 
            recurse on the right subarray
    else
        return false
}

Note: Array has to be sorted for Binary Search to work.

Binary Search can be implemented in two ways i.e recursive and iterative.

1. Iterative code:

bool BinarySearchIter(int arr[], int length, int target) 
{
    int left = 0, right = length - 1, mid;
    while (left <= right) 
    {
        /* positon of middle element */
        mid = left + (right - left) / 2;

        /* element is found */
        if (arr[mid] == target)
            return true;

        /* searching on left sub-array */
        else if (item < A[mid])
            right = mid - 1;   

        /* searching on right sub-array */
        else
            left = mid + 1;
    }
    /* element not found */
    return false;
}

2. Recursive code:

bool BinarySearchRecur(int arr[], int left, int right, int target) 
{
    if (left <= right) 
    {
        /* positon of middle element */
        int mid = left + (right - left) / 2;

        /* element is found */
        if (arr[mid] == target)
            return true;

        else if (item < arr[mid])
        {
            /* recursve call on the left sub-array */
            return BinarySearchRecur(arr, left, mid-1, target);        
        }

        else
        {
             /* recursive call on the right sub-array */
             return BinarySearchRecur(arr, mid+1, right, target);     
        }
   }
   else
        /* element not found */
        return false;
}

Time complexity of Binary Search is O(logN) where N is the size of the array. This is because after each recursion or each iteration the size of problem is reduced into half.

Explaining with a example:

Let array Arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} and we need to find 3 in array Arr. So target = 3 and length = 10

Initially,
left = 0, right = length – 1 = 10 – 1 = 9
In 1st iteration,
mid = left + (right – left) / 2 = 0 + (9 – 0) / 2 = 4
Arr[mid] ( = 4) is greater than item. Since the array A is sorted we can say that the item must be in the left sub-array.

So now,
left = 0, right = mid – 1 = 4 – 1 = 3
In 2nd iteration,
mid = left + (right – left) / 2 = 0 + (3 – 0) / 2 = 1
Arr[mid] ( = 1) is smaller than item. Since the array A is sorted we can say that the item must be in the right sub-array.

So now,
left = mid + 1 = 1 + 1 = 2, right = 3
In 3rd iteration,
mid = left + (right – left) / 2 = 2 + (3 – 2) / 2 = 2
Arr[mid] ( = 2) is smaller than item. Since the array A is sorted we can say that the item must be in the right sub-array.

So,
left = mid + 1 = 2 + 1 = 3, right = 3
In 4th iteration,
mid = left + (right – left) / 2 = 3 + (3 – 3) / 2 = 3
A[mid] ( = 3) is equal to the target, so the Binary Search function will return true and the element is found.