public class SearchComparisonLab{
    public static void main(String[] args){
        System.out.println("||==========================================||");
        System.out.printf("|| %-40s || %n", "Student Name: Faisal Majed Alghamdi");
        System.out.printf("|| %-40s || %n", "Student Number: 447001625");
        System.out.println("||==========================================||\n");

        int[] data = {3, 7, 11, 15, 19, 23, 27, 31, 35, 39};

        System.out.println("||=============(comparison)==============||");
        System.out.printf("|| %-3s || %-13s || %-13s || %n", "key", "Linear Search", "Binary Search");
        System.out.printf("|| %-3d || %-13d || %-13d || %n", 3 , linearSearchComparison(data, 3) , binarySearchComparison(data, 3));
        System.out.printf("|| %-3d || %-13d || %-13d || %n", 27 , linearSearchComparison(data, 27) , binarySearchComparison(data, 27));
        System.out.printf("|| %-3d || %-13d || %-13d || %n", 39 , linearSearchComparison(data, 39) , binarySearchComparison(data, 39));
        System.out.printf("|| %-3d || %-13d || %-13d || %n", 50 , linearSearchComparison(data, 50) , binarySearchComparison(data, 50));
        System.out.println("||===========(-1 = Not Found)============||\n");

        System.out.println("||==============(run time)===============||");
        System.out.printf("|| %-3s || %-13s || %-13s || %n", "key", "Linear Search", "Binary Search");
        System.out.printf("|| %-3d || %-13f || %-13f || %n", 3 , ((float) linearSearchComparison(data, 3))*0.000001 , ((float) binarySearchComparison(data, 3)*0.000001));
        System.out.printf("|| %-3d || %-13f || %-13f || %n", 27 , ((float) linearSearchComparison(data, 27))*0.000001 , ((float) binarySearchComparison(data, 27)*0.000001));
        System.out.printf("|| %-3d || %-13f || %-13f || %n", 39 , ((float) linearSearchComparison(data, 39))*0.000001 , ((float) binarySearchComparison(data, 39)*0.000001));
        System.out.printf("|| %-3d || %-13d || %-13d || %n", 50 , linearSearchComparison(data, 50) , binarySearchComparison(data, 50));
        System.out.println("||===========(-1 = Not Found)============||");

    }
    static int linearSearch(int[] data, int key){
        for(int i = 0; i < data.length; i++){
            if(data[i] == key){
                return i;
            }
        }
        return -1;
    }
    static int linearSearchComparison(int[] data, int key){
        int comparison = 0;
        for(int i = 0; i < data.length; i++){
            comparison++;
            if(data[i] == key){
                return comparison;
            }
        }
        return -1;
    }
    static int binarySearch(int[] data, int key){
        int low = 0;
        int high = data.length - 1;
        while(low <= high){
            int mid = low + (high - low) /2;
            if(data[mid] == key){
                return mid;
            }
            else if(data[mid] < key){
                low = mid + 1;
            }
            else{
                high = mid - 1;
            }
        }
        return -1;
    }
    static int binarySearchComparison(int[] data, int key){
        int comparison = 0;
        int low = 0;
        int high = data.length - 1;
        while(low <= high){
            comparison++;
            int mid = low + (high - low) /2;
            if(data[mid] == key){
                return comparison;
            }
            else if(data[mid] < key){
                low = mid + 1;
            }
            else{
                high = mid - 1;
            }
        }
        return -1;
    }
}