package analysis;

public class FSearch {

    public static final int NOT_FOUND = -1;

    public static void main(String[] args) {

        int a[] = { 1, 2, 4, 5, 6, 8, 9 };
        int b[] = { 1, 5, 3, 8, 2, 4, 7 };

        //Show the steps of fSearch([1 2 4 5 6 8 9], 6).
        System.out.println(fSearch(a, 6));

        //Show the steps of fSearch([1 5 3 8 2 4 7], 3).
        System.out.println(fSearch(b, 3));
    }

    public static int fSearch(int[] a, int x) {
        int low = 0;
        int high = a.length - 1;
        int mid;
        while (low <= high) {           
            mid = (low + high) / 2;
            if (x > a[mid])
                low = mid + 1;
            else if (x < a[mid])
                high = mid - 1;
            else
                return mid;
        }
        return NOT_FOUND; // NOT_FOUND = -1
    }
}