package day2;

import java.util.Scanner;

public class blockSearch {
    public static void main(String[] args) {
        int[] arr = {27, 22, 30, 40, 36,
                13, 19, 16, 20,
                7, 10,
                43, 50, 48};

        // 初始化4个块：参数（max, min, endIndex, startIndex）与原数组分块匹配
        Block b1 = new Block(40, 22, 4, 0);   // 块1：arr[0-4]
        Block b2 = new Block(20, 13, 8, 5);   // 块2：arr[5-8]
        Block b3 = new Block(10, 7, 10, 9);   // 块3：arr[9-10]
        Block b4 = new Block(50, 43, 13, 11); // 块4：arr[11-13]

        Block[] blockArr = {b1, b2, b3, b4};

        // 1. 修复Scanner使用：用try-with-resources自动关闭资源（无需手动close）
        try (Scanner scanner = new Scanner(System.in)) {
            System.out.print("请输入要查找的数字：");
            int target = scanner.nextInt(); // 读取控制台输入的整数（目标值）

            // 2. 修复参数类型：传入int类型的target，而非Scanner对象
            int index = getIndex(blockArr, arr, target);

            // 输出结果：优化提示，让结果更直观
            if (index != -1) {
                System.out.printf("查找成功！数字%d在数组中的索引为：%d%n", target, index);
            } else {
                System.out.printf("查找失败！数字%d不在数组中%n", target);
            }
        }
    }

    // 3. 修复参数名：将number改为target，与“目标查找值”含义一致
    private static int getIndex(Block[] blockArr, int[] arr, int target) {
        // 先找到目标值所在的块
        int indexBlock = findIndexBlock(blockArr, target);
        if (indexBlock == -1) { // 目标值不在任何块的范围内
            return -1;
        }

        // 获取目标块的起始/结束索引
        int startIndex = blockArr[indexBlock].getStartIndex();
        int endIndex = blockArr[indexBlock].getEndIndex();

        // 在目标块内线性查找
        for (int i = startIndex; i <= endIndex; i++) {
            if (arr[i] == target) {
                return i; // 找到目标，返回原数组索引
            }
        }

        return -1; // 目标在块范围内，但块内无此值
    }

    // 4. 修复参数名：将number改为target，保持与getIndex一致
    public static int findIndexBlock(Block[] blockArr, int target) {
        for (int i = 0; i < blockArr.length; i++) {
            // 判断目标值是否在当前块的[min, max]范围内
            if (target >= blockArr[i].getMin() && target <= blockArr[i].getMax()) {
                return i; // 返回块的索引
            }
        }
        return -1; // 目标值不在任何块的范围内
    }
}

// 块类：保持原封装逻辑不变
class Block {
    private int max;       // 块内最大值
    private int min;       // 块内最小值
    private int endIndex;  // 块在原数组的结束索引（含）
    private int startIndex;// 块在原数组的起始索引（含）

    // 构造方法：初始化块的属性
    public Block(int max, int min, int endIndex, int startIndex) {
        this.max = max;
        this.min = min;
        this.endIndex = endIndex;
        this.startIndex = startIndex;
    }

    // Getter方法：保持原逻辑不变
    public int getMax() {
        return max;
    }

    public void setMax(int max) {
        this.max = max;
    }

    public int getMin() {
        return min;
    }

    public void setMin(int min) {
        this.min = min;
    }

    public int getEndIndex() {
        return endIndex;
    }

    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }

    public int getStartIndex() {
        return startIndex;
    }

    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }
}

package Searching;

import java.util.Arrays;

public class Fibonaccialo {
    public static void main(String[] args) {
        int arr[] = {2,4,9,10,13,15,16,19,34};
        System.out.println(FibonacciSearch(arr,34)+1);
    }

    //创建斐波那契数列
    public static int[] Fibonacci(int n) {
        int[] FibonacciList = new int[n];
        FibonacciList[0] = 0;
        FibonacciList[1] = 1;
        for (int i = 2; i < n; i++) {
            FibonacciList[i] = FibonacciList[i - 1] + FibonacciList[i -2];
        }
        return FibonacciList;
    }

    //斐波那契查找，返回的是value在list中的索引值，所以在最后可以加一，为了看出效果，我在上面打印的时候再加一
    public static int FibonacciSearch(int[] list,int value)
    {
        int low = 0;
        int high = list.length -1;
        int k = 0;//表示斐波那契分割的值
        int mid = 0;//存放黄金分割点的值
        int f[] = Fibonacci(20);//斐波那契数列
        //找k值
        while (high>f[k] - 1){
            k++;
        }
        //复制到新的数组
        int temp[] = Arrays.copyOf(list,f[k]);
        //得到f[k]的值可能会大于a的长度,将新数组的多余的部分用数组中的最后一个数字填充
        for (int i = high+1; i <temp.length ; i++) {
            temp[i] = list[high];
        }
        //使用while循环，找到value的位置
        while (low<=high){//满足这个条件就可以继续找
            mid = low+f[k-1]-1;//找到的黄金分割点
            if(value<temp[mid]){
                high = mid - 1;
                k--;
            }else if(value>temp[mid]){
                low = mid + 1;
                k-=2;
            }else{
                if(mid<=high){
                    return mid;
                }else {
                    return high;
                }
            }
        }
        return -1;
    }

}