public class KboatBinarySearch
{
    public int binSearch(int arr[], int item)    {
        int l = 0, index = -1;
        int h = arr.length - 1;

        System.out.println("Searching for " + item);
        while (l <= h) {
            int m = (l + h) / 2;
            System.out.println("Searching in sub-array :");
            for(int i = l; i < h; i++)
                System.out.print(arr[i] + " ");
            
            System.out.println();
            
            System.out.println("Comparing " + item + " with "
                                + arr[m] + " at index " + m);
            
            if (arr[m] < item)
                l = m + 1;
            else if (arr[m] > item)
                h = m - 1;
            else {
                index = m;
                break;
            }
        }
        return index;
    }
    
    public static void main(String args[]) {
        KboatBinarySearch obj = new KboatBinarySearch();
        
        int X[] = {3, 4, 7, 11, 18, 29, 45, 71, 87, 89, 93, 96, 99};
        
        int index = obj.binSearch(X, 66);
        if (index == -1) {
            System.out.println("66 not found");
        }
        else {
            System.out.println("66 found at index " + index);
        }
        
        index = obj.binSearch(X, 71);
        if (index == -1) {
            System.out.println("71 not found");
        }
        else {
            System.out.println("71 found at index " + index);
        }
        
    }
}