public class Search {

    /*
     * Used to avoid the penalty time of loading the class
     */
    public static void dummy()
    {
    }

    /**
     * Linear search
     *
     * @param A     -array to search
     * @param value - value to search
     * @return index if target is in A, -1 otherwise
     */
    public static int linearSearch(int[] A, int value)
    {
        for (int i = 0; i < A.length; i++) {
            if (A[i] == value) {
                return i;
            }
        }

        return -1;
    }

    /**
     * Binary search
     *
     * @param A      - array to search (must be sorted in ascending order)
     * @param target - value to search
     * @return index if target is in A, the insertion index otherwise
     */
    public static int binarySearch(int[] A, int target)
    {
        int min = 0;
        int max = A.length - 1;
        while (min <= max) {
            int mid = (min + max) / 2;
            if (A[mid] < target) {
                min = mid + 1;
            }
            else if (A[mid] > target) {
                max = mid - 1;
            }
            else {
                return mid;
            }
        }

        return -(min + 1);
    }
}