public class LinearSearch {
    /**
     * @param a Array of unsorted integers
     * @param val The value to search for
     * @return Array's index if found; -1 if not found. 
     */
    private static int search(int[] a, int val)
    {
        for(int k=0; k<a.length; k++){
            if(val==a[k])
                return k;
        }
        return -1;  // not found
    }
}

public class BinarySearch {
    /**
     * @param a Array of sorted integers
     * @param val The value to search for
     * @param lo Low index of array
     * @param hi High index of array
     * @return Array's index if found; -1 if not found. 
     */
    public static int search(int[] a, int val, int lo, int hi)
    {
        while(lo<=hi){
            int mid = (lo + hi) >>> 1;
            int midVal = a[mid];
            if(val == midVal){
                return mid;
            }else if(val < midVal){
                hi = mid-1;
            }else{
                lo = mid+1;
            }
        }
        return -1;  // not found
    }

    /**
     * @param a Array of sorted integers
     * @param val The value to search for
     * @param lo Low index of array
     * @param hi High index of array
     * @return Array's index if found; -1 if not found. 
     */
    public static int searchWithRecursive(int[] a, int val, int lo, int hi)
    {
        int mid = (lo + hi) >>> 1;
        int midVal = a[mid];
        if(val == midVal)
            return mid;
        
        if(val < midVal)
            return searchWithRecursive(a, val, lo, mid-1);
        else
            return searchWithRecursive(a, val, mid+1, hi);
    }