/**
 * 顺序查找
 * @param array 查找的数组
 * @param value 查找的值
 * @return 数组内有和查找值匹配的值则返回数组内匹配值的下标，反之则返回-1
 */
public static int orderSearch(int[] array, int value){
    //遍历数组中的所有数据，当有能和value匹配的数据时，返回该数据的数组下标
    for (int i=0; i<array.length; i++){
        if (array[i] == value){
            return i;
        }
    }
    //当数组中没有能和value匹配的数据时，返回-1
    return -1;
}

/**
 * 二分查找（查找的数组必须是有序数组）
 * @param array 查找的数组
 * @param left 中间值的左标(该次递归操作数组段的最左端下标)
 * @param right 中间值的右标(该次递归操作数组段的最右端下标)
 * @param findValue 查找的值
 * @return 数组内有和查找值匹配的值则返回数组内匹配值的下标，反之则返回-1
 */
public static int binarySearch(int[] array, int left, int right, int findValue){
    if (left > right){//判断是否已经查找到尽头
        return -1;
    }
    int mid = (left + right)/2;//取中间值下标
    if (findValue > array[mid]){//如果findValue>array[mid] 则从中间值向右递归
        return binarySearch(array, findValue, mid+1, right);
    }else if (findValue < array[mid]){//如果findValue<array[mid] 则从中间值向左递归
        return binarySearch(array, findValue, left, mid);
    }else {//findValue==array[mid]时，则匹配成功，返回mid下标
        return mid;
    }
}

/**
 * 插值查找（查找的数组必须是有序数组）
 * @param array 查找的数组
 * @param left 查找段的最小值索引下标，即查找段内最左下标
 * @param right 查找段的最大值索引下标，即查找段内最右下标
 * @param findValue 查找的值
 * @return 数组内有和查找值匹配的值则返回数组内匹配值的下标，反之则返回-1
 */
public static int insertSearch(int array[], int left, int right, int findValue){
    //当左标left大于右标right时，即查找已经遍历到数组的尽头，则返回-1
    //当查找值findValue小于数组内最小值或大于数组内最大值时，即数组内没有能匹配的值，则返回-1
    if (left>right || findValue<array[0] || findValue>array[array.length-1]){
        return -1;
    }
    //使用插值公式求出中间值位置下标
    int mid = left + (right-left) * (findValue-array[left]) / (array[right]-array[left]);
    if (findValue < array[mid]){//当查找值小于中间中间值时，向左递归查找
        return insertSearch(array, left, mid-1, findValue);
    }else if (findValue > array[mid]){//当查找值大于中间值时，向右递归查找
        return insertSearch(array, mid+1, right, findValue);
    }else {//当查找值等于中间值时，则返回中间值下标
        return mid;
    }
}

/**
 * 斐波那契查找（查找数组必须是有序数组）
 * @param array 查找的数组
 * @param findValue 查找的值
 * @return 数组内有和查找值匹配的值则返回数组内匹配值的下标，反之则返回-1
 */
public static int fibonacciSearch(int array[], int findValue){
    int low = 0;//查找段的最小值索引下标，即查找段内最左下标
    int high = array.length-1;//查找段的最大值索引下标，即查找段内最右下标
    int mid = 0;//储存中间值的下标
    int k = 0;//斐波那契数组的下标索引
    int fib[] = fib();//斐波那契数列数组
 
    /*
    获取和查找数组最接近且大于查找数组最右下标的斐波那契数组的值，以作为新数组的长度
    因为斐波那契的值fib[k]对应的是数组的长度，而右标high对应的是数组下标,
    所以比较时，fib[k]的值需要-1
     */
    while (high > fib[k]-1){
        k++;
    }
    //将查找的数组复制到新的数组，长度为前面求出的斐波那契数组值fib[k]
    int temp[] = Arrays.copyOf(array, fib[k]);
    /*
    因为fib[k]不一定等于查找数组的长度，所以在最右下标high右边，
    即超出查找数组的部分，把它们的值都设为最右下标的值temp[high]
     */
    for (int i=high+1; i<temp.length-1; i++){
        temp[i] = temp[high];
    }
    /*
    在斐波那契查找中是按照斐波那契数列的黄金分割点来划分查找数组的，
    而在斐波那契数列中 fib[k] = fib[k-1]+fib[k-2],
    所以可以把查找数组分成俩部分fib[k-1]和fib[k-2]，因此
    黄金分割点,即中间值的下标mid = low+fib[k-1]-1，
    向左递归部分 = fib[k-1]，向右递归部 = fib[k-2]
     */
    while (low <= high){//判断是否查找到尽头
        /*
        low：随着向右递归而发生变化，使得中间值可以跟着适应
        fib[k-1]-1：因为斐波那契数列数组中的值对应的是数组长度，所以需-1
         */
        mid = low + fib[k-1] -1;
        if (findValue < temp[mid]){//查找值小于中间值，向左递归
            high = mid-1;//重新设置查找数组右标，设置新的查找段
            k -=1; //因为是向左递归,对应的是fib[k-1],所以斐波那契数组的下标k要-1
        }else if (findValue > temp[mid]){//查找值大于于中间值，向右递归
            low = mid+1;//重新设置查找数组的左标，设置新的查找段
            k -=2;//因为是向右递归,对应的是fib[k-2],所以斐波那契数组的下标k要-2
        }else {//当查找值等于中间值时，即匹配成功
            /*
            因为临时数组temp的长度可能超过原先的查找数组,而超出部分的值都等于右标位置的值，
            所以当匹配成功值的下标大于右标时，要返回右标high，反之则之间返回中间值下标mid即可
             */
            if (mid <= high){
                return mid;
            }else {
                return high;
            }
        }
    }
    //数组内无匹配成功的值，则返回-1
    return -1;
}
//获取斐波那契数列
public static int[] fib(){
    int fib[] = new int[20];
    fib[0] = 1;
    fib[1] = 1;
    for (int i=2; i<fib.length; i++){
        fib[i] = fib[i-1] + fib[i-2];
    }
    return fib;
}

public class BlockSearch {
    public static void main(String[] args) {
        int[] array = new int[50];
        for (int i=0; i<array.length; i++){
            array[i] = (int)(Math.random() * 100);
        }
        System.out.println(Arrays.toString(array));
        List<Block> blockTable = createBlockTable(array);
        System.out.println(blockSearch(array, 10, blockTable));
    }
    /**
     * 将数组分成多块，并创建块索引表储存各块的最大值和起始位置
     * @param array 查找的数组
     * @return 返回块索引表
     */
    public static List<Block> createBlockTable(int[] array){
        int nums = 10;//每块储存的数据数量
        int start = 0;//块的起始位置，初始为0
        int maxValue = 0;//块中的最大值
        List<Block> blockTable = new ArrayList<>();//块索引表
        
        while (start < array.length){//判断起始起始位置是否大于查找数组的长度
            maxValue = array[start];//假定块中的最大值为起始位置的值
            //判断剩余的数组长度是否小于每块储存的初始数据量，
            //如果大于则的块的长度为初始数据量，如果大于则最后一块的长度就是剩余的数组长度
            int maxLength = (start+nums) < array.length ? (start+nums) : array.length;
            //遍历块中的元素，选出块中的最大值
            for (int i=start; i<maxLength; i++){
                if (maxValue < array[i]){
                    maxValue = array[i];
                }
            }
            //将块中的最大值和起始位置添加进块索引表
            //注意：块中的数据与块的索引对于查找数组来说是有序的，即是按照查找数组的原始顺序来排序的
            blockTable.add(new Block(start, maxValue));
            //移动到下一块的起始位置
            start += nums;
        }
        return blockTable;
    }
    /**
     * 分块查找
     * @param array 查找数组
     * @param findValue 查找的值
     * @param blockTable 块索引表
     * @return 数组内有和查找值匹配的值则返回数组内匹配值的下标，反之则返回-1
     */
    public static int blockSearch(int[] array, int findValue, List<Block> blockTable){
        int blockIndex = 0;//块索引表中块的索引，按顺序遍历，初始值为0
        //判断查找值是否大于块中的最大值，如果大于则移动到下一块
        while (blockIndex < blockTable.size() && findValue > blockTable.get(blockIndex).maxValue){
            blockIndex++;
        }
        //当块的索引大于块索引表的大小时，即说明查找值大于查找数组中的最大值，数组中没有查找值
        if (blockIndex > blockTable.size()-1){
            return -1;
        }
        //从块的起始位置开始在查找数组中进行查找，这时查找长度比顺序查找的长度缩短了start+1
        for (int i=blockTable.get(blockIndex).start; i<array.length; i++){
            //当从数组中匹配到查找值时，返回该匹配值在数组中的下标
            if (array[i] == findValue){
                return i;
            }
        }
        //当查找数组中无与查找值匹配的值时，返回-1
        return -1;
    }
}
//块
class Block{
    int start;//起始位置
    int maxValue;//块中的最大值
 
    public Block(int start, int maxValue) {
        this.start = start;
        this.maxValue = maxValue;
    }
}