/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author om
 */

import java.util.ArrayList;
import java.util.Comparator;

public class RecursiveBinarySearch2 <T>{

    public static int recursiveBinarySearch(Comparable[] arr, Comparable val, int fl, int rf)
                                                throws ObjectNotFoundException {
        if (fl > rf){
            throw new ObjectNotFoundException();
        }

        int guess  = (rf - fl)/2 + fl;

        int relation = val.compareTo(arr[guess]);

        if(relation < 0){
            return recursiveBinarySearch(arr, val, fl, guess--);
        }

        if(relation > 0){
            return  recursiveBinarySearch(arr, val, guess++, rf);
        }

        return guess;
    }

    public static int recursiveBinarySearch(ArrayList<Comparable> al, Comparable val, int fl, int rf)
                                                 throws ObjectNotFoundException{
        Comparable[] arr = new Comparable[al.size()];
        return recursiveBinarySearch(al.toArray(arr), val, fl, rf);

    }

    public static int recursiveBinarySearch(ArrayList<Comparable> al, Comparable val)
                                                 throws ObjectNotFoundException{
        return recursiveBinarySearch(al, val, 0, al.size());
    }

    public static int recursiveBinarySearch(Comparable[] arr, Comparable val)
                                                 throws ObjectNotFoundException{
        return recursiveBinarySearch(arr, val, 0, arr.length);
    }

    public int recursiveBinarySearch(T[] arr, T val, Comparator<T> cmp, int fl, int rf)
                                                throws ObjectNotFoundException {
        if (fl > rf){
            throw new ObjectNotFoundException();
        }

        int guess  = (rf - fl)/2 + fl;

        int relation = cmp.compare(val, arr[guess]);

        if(relation < 0){
            return recursiveBinarySearch(arr, val, cmp, fl, guess--);
        }

        if(relation > 0){
            return  recursiveBinarySearch(arr, val, cmp, guess++, rf);
        }

        return guess;
    }


}