import java.util.ArrayList;
import java.util.Scanner;

class LinearSearch {
    /**
     * 线性搜索
     * @param list 要搜索的数组
     * @param target 要搜索的目标
     * @return 目标在数组中的索引，如果不存在则返回 -1
     */
    public static int search(ArrayList<Integer> list, int target) {
        for (int i = 0; i < list.size(); i++) { // 遍历数组
            if (list.get(i) == target) { // 如果找到目标
                return i; // 返回目标的索引
            }
        }
        return -1; // 如果循环完整结束了，则代表没有找到目标，返回 -1
    }

    public static int recursiveSearch(ArrayList<Integer> list, int target, int index) {
        if (index == list.size()) {
            return -1;
        }
        if (list.get(index) == target) {
            return index;
        }
        return recursiveSearch(list, target, index + 1);
    }
}

class JumpSearch {
    /**
     * 跳跃搜索
     * @param list 要搜索的数组
     * @param target 要搜索的目标
     * @return 目标在数组中的索引，如果不存在则返回 -1
     */
    public static int search(ArrayList<Integer> list, int target) {
        int step = (int) Math.sqrt(list.size()); // 获取步长

        int idx; // 索引
        for (idx = 0; idx < list.size(); idx += step) { // 以步长为单位遍历数组
            if (list.get(idx) == target) { // 如果找到目标
                return idx; // 返回目标的索引
            }
            if (list.get(idx) > target) { // 如果当前元素大于目标，则目标在当前元素之前，上次检查的元素之后
                break; // 结束以步长为单位的遍历
            }
        }

        for (int i = idx - step; i < idx; i++) { // 回退一个步长，回到上次检查的元素，遍历这个步长内的元素
            if (list.get(i) == target) { // 如果找到目标
                return i; // 返回目标的索引
            }
        }

        return -1; // 如果循环完整结束了，则代表没有找到目标，返回 -1
    }

    public static int recursiveSearch(ArrayList<Integer> list, int target, int index, int step) {
        if (index >= list.size() || list.get(index) > target) {
            if (step == 1) {
                return -1;
            }
            return recursiveSearch(list, target, index - step, 1);
        }
        if (list.get(index) == target) {
            return index;
        }
        return recursiveSearch(list, target, index + step, step);
    }
}

class BinarySearch {
    /**
     * 二分搜索
     * @param list 要搜索的数组
     * @param target 要搜索的目标
     * @return 目标在数组中的索引，如果不存在则返回 -1
     */
    public static int search(ArrayList<Integer> list, int target) {
        int low = 0; // 低位索引
        int high = list.size() - 1; // 高位索引

        while (low <= high) { // 当低位索引小于等于高位索引时，才有元素可以搜索
            int mid = (low + high) / 2; // 计算中间索引
            if (list.get(mid) == target) { // 如果找到目标
                return mid; // 返回目标的索引
            } else if (list.get(mid) < target) { // 如果中间元素小于目标，则目标在中间元素之后
                low = mid + 1; // 低位索引更新为中间索引加一，在中间元素之后的元素中搜索
            } else { // 如果中间元素大于目标，则目标在中间元素之前
                high = mid - 1; // 高位索引更新为中间索引减一，在中间元素之前的元素中搜索
            }
        }

        return -1; // 如果循环完整结束了，则代表没有找到目标，返回 -1
    }

    public static int recursiveSearch(ArrayList<Integer> list, int target, int low, int high) {
        if (low > high) {
            return -1;
        }
        int mid = (low + high) / 2;
        if (list.get(mid) == target) {
            return mid;
        } else if (list.get(mid) < target) {
            return recursiveSearch(list, target, mid + 1, high);
        } else {
            return recursiveSearch(list, target, low, mid - 1);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(5);
        list.add(8);
        list.add(13);
        list.add(21);
        list.add(55);
        list.add(77);
        list.add(89);
        list.add(101);
        list.add(201);
        list.add(256);
        list.add(780);
        list.add(1024);
        list.add(65536);
        list.add(66666);

        System.out.println(list);

        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the target: ");
        int target = scanner.nextInt();

//        int index = LinearSearch.search(list, target);
//        int index = JumpSearch.search(list, target);
//        int index = BinarySearch.search(list, target);
//        int index = LinearSearch.recursiveSearch(list, target, 0);
        int index = JumpSearch.recursiveSearch(list, target, 0, (int) Math.sqrt(list.size()));
//        int index = BinarySearch.recursiveSearch(list, target, 0, list.size() - 1);

        if (index == -1) {
            System.out.println("Not Found");
        } else {
            System.out.println("Found at index " + index);
        }
    }
}