Binary Search Algorithm: Recursive Implementation.

Binary Search: Binary Search is the process of searching an element form sorted array by repeatedly dividing the search interval in half. Binary Search is faster than Linear Search. It only works on sorted arrays. Time complexity for Binary Search is O(log N). In Binary Search, we basically ignore half of the elements just after first comparison. Following steps should be followed while doing Binary Search.

Algorithm:

1. Compare x(element to be searched)with Middle element.
2. If x matches with middle element, we return mid index.
3. Else if x is greater than the mid element, then x can lie only lie in right of the array after the mid element(mid+1). So we recur for right half.
4. Else x is smaller than mid, we recur to left half (mid-1).

Code Implementation:

public class BinarySearch {

    public int binarySearch(int arr[], int l, int r, int x) {

        if (r >= l) // r should not cross l (base case)

        {

            // here l points to left indices and r points to rigth indices

            int mid = (l + r) / 2; // l+(r-l)/2

            // if element is present at middle

            if (arr[mid] == x)

                return mid;

            // if element is smaller than mid, then

            // it can be only present to left of sub array

            if (x < arr[mid])

                return binarySearch(arr, l, mid - 1, x);

            // else the element can be present in right subarray

            if (x > arr[mid])

                return binarySearch(arr, mid + 1, r, x);

        }

        // we reach here when element is not present

        return -1;

    }

    public static void main(String[] args) {

        BinarySearch ob = new BinarySearch();

        int arr[] = { 2, 3, 5, 7, 8, 9 };

        int x = 9; // element to be searched

        int n = arr.length;

        // result will store the returned value

        int result = ob.binarySearch(arr, 0, n - 1, x);

        if (result == -1) {

            System.out.println("Element not Present");

        } else {

            System.out.println("Element is found at index: " + result);

        }

    }

}

Output:

Element is found at index: 5