import java.util.Arrays;
import java.util.Scanner;
import java.util.InputMismatchException;
import java.util.function.BiFunction;

class Array {
    private double[] arr;
    Array() throws Exception {
        takeInput();
    }
    void takeInput() throws Exception {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the length: ");
        int size = sc.nextInt();
        if (size < 0)
            throw new Exception("Array length can not be negative");
        arr = new double[size];
        System.out.print("Enter the array elements: ");
        for (int i = 0; i < size; i++)
            arr[i] = sc.nextDouble();
    }
    void display() {
        System.out.print("The array elements are:");
        for (int i = 0; i < arr.length; i++)
            System.out.print(" " + arr[i]);
        System.out.println();
    }
    double get(int i) throws IndexOutOfBoundsException {
        return arr[i];
    }
    void set(int i, double val) throws IndexOutOfBoundsException {
        arr[i] = val;
    }
    void sort() {
        Arrays.sort(arr);
    }
    int size() { return arr.length; }
}

class ArrayOperations {
    static int linearSearch(Array arr, double item) {
        int size = arr.size();
        for (int i = 0; i < size; i++) {
            if (arr.get(i) == item)
                return i;
        }
        return -1;
    }
    static int binarySearch(Array arr, double item) {
        int size = arr.size();
        int leftIndex = 0, rightIndex = size - 1;
        while (leftIndex <= rightIndex) {
            int midIndex = leftIndex + (rightIndex - leftIndex) / 2;
            double midValue = arr.get(midIndex);
            if (item == midValue) {
                return midIndex;
            } else if (item < midValue) {
                rightIndex = midIndex - 1;
            } else {
                leftIndex = midIndex + 1;
            }
        }
        return -1;
    }
}

class ArraySearch {
    static void menu() {
        System.out.println(
            "Menu:\n" +
            " 1. Re-enter array\n" +
            " 2. Display array elements\n" +
            " 3. Perform linear search\n" +
            " 4. Perform binary search\n" +
            " 5. Exit\n");
    }
    static void performSearch(Scanner sc, Array arr, BiFunction<Array, Double, Integer> searcher) {
        arr.display();
        System.out.print("Enter the element to find: ");
        double elem = sc.nextDouble();
        int idx = searcher.apply(arr, elem);
        if (idx == -1) {
            System.out.println("The element " + elem + " was not found in the array.");
        } else {
            System.out.println("The element " + elem + " was found in the array at position " + (idx + 1) + ".");
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Menu-driven program of array searching\n");
        System.out.println("Enter the array:");
        Array arr = null;
        while (true) {
            try {
                if (arr == null) arr = new Array();
                menu();
                System.out.print("Enter your choice: ");
                int choice = sc.nextInt();
                switch (choice) {
                case 1:
                    arr.takeInput();
                    arr.display();
                    break;
                case 2:
                    arr.display();
                    break;
                case 3:
                    performSearch(sc, arr, ArrayOperations::linearSearch);
                    break;
                case 4:
                    System.out.println("Array is sorted before binary search.");
                    arr.sort();
                    performSearch(sc, arr, ArrayOperations::binarySearch);
                    break;
                case 5:
                    System.out.println("Bye.");
                    return;
                default:
                    System.out.println("Invalid choice, try again.");
                }
            } catch (InputMismatchException e) {
                System.err.println("Error: Invalid input, try again");
                sc.nextLine();
            } catch (Exception e) {
                System.err.println("Error: " + e.getMessage());
            }
        }
    }
}