Binary Search

Given a sorted array arr[] of n elements, write a function to search a given element x in arr[].

A simple approach is to do linear search, i.e., start from the leftmost element of arr[] and one by one compare x with each element of arr[], if x matches with an element, return the index. If x doesn’t match with any of elements, return -1.
The time complexity in linear search is O(n).

The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Logn).

/**
 * Given a sorted array arr[] of n elements, write a function to search a given element n in arr[]
 */
public class BinarySearch {

    public static void main(String a[]){

        int[] arr = new int[]{2,5,6,9,10,54,100,121,150,181};
        BinarySearch obj = new BinarySearch();
        System.out.println(obj.binarySearchRecursive(arr,0,arr.length,150));
        System.out.println(obj.binarySearchIterative(arr,121));
    }

    private int binarySearchIterative(int[] arr, int n) {
        int l=0, r = arr.length;
        int mid=0;
        while(l <= r){
            mid = l + (r - l)/2;
            if(n == arr[mid]){
                return mid;
            }else if(n > arr[mid]){
                l = mid + 1;
            }else if(n < arr[mid]){
                r = mid - 1;
            }
        }
        return -1;
    }

    private int binarySearchRecursive(int[] arr, int l, int r, int n) {
        if(r >= l){
            int mid = l + (r - l)/2;
            if(arr[mid] == n){
                return mid;
            }else if(arr[mid] < n){
                return binarySearchRecursive(arr,mid+1,r,n);
            }else if(arr[mid] > n){
                return binarySearchRecursive(arr,l,mid-1,n);
            }
        }
        return -1;
    }
}