Binary Search

Binary search, also known logarithmic search or half-interval search, is a "Divide and Conquer" search algorithm that finds the position of a target value within a sorted array in run-time complexity of Ο(log n). It is one of the fundamental algorithms in Computer Science. For this algorithm to work properly the data collection should be in sorted form.

Binary search searches for a particular item by comparing it with the middle element of the array. If match occurs, then index of the middle element is returned. If the item is smaller than the middle element, then it is searched in the left sub-array of the middle element, otherwise the item is searched in the right sub-array of the middle element. This process continues on the sub-arrays as well, till the item is found or the size of sub-array reduces to zero.

(Image from Wikipedia)

Time Complexity: O(log n)
Space Complexity: O(1) in iterative implementation and O(log n) in recursive implementation (considering the recursion call stack space).

Both iterative and recursive implementations of Binary Search are shown here:

1. Iterative Binary Search:

int binarySearch(int *A, int size, int item)
{
    int start = 0, end = (size - 1), mid;

    while(start <= end)
    {
        mid = (start + end) / 2;

        if(A[mid] == item)
            return mid;            // Item found at index mid

        else if(A[mid] > item)
            end = mid - 1;         // Item may be on the left sub-array

        else
            start = mid + 1;       // Item may be on the right sub-array
    }

    return -1;    // Not found
}

2. Recursive Binary Search:

int binarySearch(int *A, int start, int end, int item)
{
    int mid;

    if(start <= end)
    {
        mid = (start + end) / 2;

        if(A[mid] == item)
            return mid;

        else if(A[mid] > item)
            return binarySearch(A, start, mid-1, item);

        else
            return binarySearch(A, mid+1, end, item);
    }

    return -1;
}

Note: The above Binary Search algorithms may fail in some cases. See this post for detail: There may be a bug hidden in your Binary Searches and Merge Sorts!