标签：int max 常见 number mid 算法 public Block

基本查找

public class A01_BasicSearchDemo1 {
    public static void main(String[] args) {
        //基本查找\顺序查找
        //核心:
        //从0索引开始按个往后查找
        //需求:定义一个方法利用基本查找,查询某个元素是否存在
        //数据如下:{131,127,147,81,103,23,7,79}
        int[] list = {131,127,147,81,103,23,7,79};
        boolean b = BasicSearch(list,22);
        if (b){
            System.out.println("存在");
        }else {
            System.out.println("不存在");
        }
    }
    public static boolean BasicSearch(int[] list,int number){
        for (int i = 0; i < list.length; i++) {
            if (list[i]==number){

                return true;
            }
        }
        return false;
    }
}

二分查找\折半查找

前提条件:数组中的数据必须是有序的

如果数据是乱的,先排序再用二分查找得到的索引没有实际意义,只能确定当前数字在数组中是否存在,因为排序之后数组的位置就可以发生变化了

核心逻辑:每次排除一半的查找范围

优势:提高查找效率

public class A02_BinarySearchDemo1 {
    public static void main(String[] args) {
        //需求:定义一个方法利用二分查找,查询某个元素在数组中的索引
        //数据如下:{7,23,79,81,103,127,131,147}
        int[] list = {7,23,79,81,103,127,131,147};
        System.out.println(BinarySearch(list, 82));
    }
    public static int BinarySearch(int[] list,int number){
        //定义两个变量记录要查找的范围
        int min = 0;
        int max =list.length-1;
        //2.利用循环不断的去找要查找的数据
        while (true){
            if (min>max){
                return -1;
            }
            //找数据
            int mid = (min + max) / 2;
            //4.拿着mid指向的元素跟要查找的元素进行比较
            //4.1number在mid的左边
            //4.2number在mid的右边
            //4.3number和mid指定的元素一样
           if (list[mid]>number){
               //4.1number在mid的左边
               //min不变,max=mid-1
                max=mid-1;
            }else if (list[mid]<number){
               //4.2number在mid的右边
               //ma
               //max不变,min=mid+1
                min=mid+1;
            }else {
               //找到了
                return mid;
            }
        }
    }
}

插值查找

要求:数组里的数据分布均匀

public class A02_BinarySearchDemo1 {
    public static void main(String[] args) {
        //需求:定义一个方法利用二分查找,查询某个元素在数组中的索引
        //数据如下:{7,23,79,81,103,127,131,147}
        int[] list = {7,23,79,81,103,127,131,147};
        System.out.println(BinarySearch(list, 81));
    }
    public static int BinarySearch(int[] list,int number){
        //定义两个变量记录要查找的范围
        int min = 0;
        int max =list.length-1;
        //2.利用循环不断的去找要查找的数据
        while (true){
            if (min>max){
                return -1;
            }
            //找数据
            int mid = min+(number-list[min])/(list[max]-list[min])*(max-min);
            //4.拿着mid指向的元素跟要查找的元素进行比较
            //4.1number在mid的左边
            //4.2number在mid的右边
            //4.3number和mid指定的元素一样
           if (list[mid]>number){
               //4.1number在mid的左边
               //min不变,max=mid-1
                max=mid-1;
            }else if (list[mid]<number){
               //4.2number在mid的右边
               //ma
               //max不变,min=mid+1
                min=mid+1;
            }else {
               //找到了
                return mid;
            }
        }
    }
}

斐波那契查找

小结

1.二分查找、插值查找、斐波那契查找各自的特点

相同点:

都是通关不断的缩写范围来查找对应的数据的

不同点

计算mid的方式不一样

二分查找:mid每次都是指向范围的中间位置

插值查找:mid尽可能的靠近要查找的数据,但是要求数据尽可能的分布均匀

斐波那契查找：根据黄金分割点来计算mid指向的位置

分块查找

无序中带着有序

分块的原则1:前一块中的最大数据,小于后一块中所有的数据(块内无序,快间有序)

分块的原则2：块数量一般等于数字的个数开根号。比如:16个数字一般分为4块左右

核心思想:先确定要查找的元素在那一块,然后再块内按个查找

public class A03_BlockSearchDemo {
    public static void main(String[] args) {
        /*
        实现步骤:
            1.创建数组blockArr存放每一个块对应的信息
            2.先查找blockArr确定要查找的数据属于那一块
            3.再单独遍历这一块数据即可
         */
        //1.要把数据进行分块
        //要分为几块:18开根号  4.24块
        int[] arr = {16,5,9,12,21,18,
                     32,23,37,26,45,34,
                     50,48,61,52,73,66};
       //创建三个块的对象
        Block b1 = new Block(21,0,5);
        Block b2 = new Block(45,6,11);
        Block b3 = new Block(73,12,17);
        //定义一个数组用来管理三个块的对象(索引表)
        Block[] blockArr = {b1,b2,b3};
        //定义一个变量组来记录要查找的元素
        int number = 48;
        //调用方法,传递索引表,数组,要查找的元素
        int index=getIndex(blockArr,arr,number);
        System.out.println(index);

    }
    //利用分块查找的原理,查询number的索引
    private static int getIndex(Block[] blockArr, int[] arr, int number) {
        //1.确定number是在那一块当中
        int indexBlock = findIndexBlock(blockArr, number);
        if (indexBlock==-1){
            //表示number不在数组当中
            return -1;
        }
        //获取这一块的其实索引和结束索引
        int startIndex = blockArr[indexBlock].getStartIndex();
        int endIndex = blockArr[indexBlock].getEndIndex()
                ;
        //3.遍历
        for (int i = startIndex; i < endIndex; i++) {
            if (arr[i]==number){
                return i;
            }
        }
        return -1;
    }
    //定义一个方法,用来确定number在那一块当中
    public static int findIndexBlock(Block[] blockArr,int number){
//        Block b1 = new Block(21,0,5);      -----0
//        Block b2 = new Block(45,6,11);     -----1
//        Block b3 = new Block(73,12,17);    -----2
        //从0开始遍历blockArr,如果number小于max,那么就表示number是在这一块当中的
        for (int i = 0; i < blockArr.length; i++) {
            if (number<=blockArr[i].getMax()){
                return i;
            }
        }
        return -1;
    }
}
class Block{
    private int max;//最大值
    private int startIndex;//初始索引
    private int endIndex;//结束索引
    public Block() {
    }
    public Block(int max, int startIndex, int endIndex) {
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }
    public int getMax() {
        return max;
    }
    public void setMax(int max) {
        this.max = max;
    }
    public int getStartIndex() {
        return startIndex;
    }
    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }
    public int getEndIndex() {
        return endIndex;
    }
    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }
    public String toString() {
        return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
    }
}

扩展的分块查找(无规律的数据)

需要额外定义一个变量min记录最小值,且各个最大值、最小值不能有交集

public class A03_BlockSearchDemo {
    public static void main(String[] args) { 
        int[] arr2 = {27,22,30,40,36,
                      13,19,16,20,
                      7,10,43,50,48};
        //创建三个块的对象
        Block b1 = new Block(22,40,0,4);
        Block b2 = new Block(13,20,5,8);
        Block b3 = new Block(7,10,9,10);
        Block b4 = new Block(43,50,11,13);
        //定义一个数组用来管理三个块的对象(索引表)
        Block[] blockArr = {b1,b2,b3,b4};
        //定义一个变量组来记录要查找的元素
        int number = 48;
        //调用方法,传递索引表,数组,要查找的元素
        int index=getIndex(blockArr,arr2,number);
        System.out.println(index);

    }
    //利用分块查找的原理,查询number的索引
    private static int getIndex(Block[] blockArr, int[] arr, int number) {
        //1.确定number是在那一块当中
        int indexBlock = findIndexBlock(blockArr, number);
        if (indexBlock==-1){
            //表示number不在数组当中
            return -1;
        }
        //获取这一块的其实索引和结束索引
        int startIndex = blockArr[indexBlock].getStartIndex();
        int endIndex = blockArr[indexBlock].getEndIndex();
        //3.遍历
        for (int i = startIndex; i <= endIndex; i++) {
            if (arr[i]==number){
                return i;
            }
        }
        return -1;
    }
    //定义一个方法,用来确定number在那一块当中
    public static int findIndexBlock(Block[] blockArr,int number){
        //从0开始遍历blockArr,如果number小于max,那么就表示number是在这一块当中的
        for (int i = 0; i < blockArr.length; i++) {
            if (number>=blockArr[i].getMin() && number<=blockArr[i].getMax()){
                return i;
            }
        }
        return -1;
    }
}
class Block{
    private int min;//最小值
    private int max;//最大值
    private int startIndex;//初始索引
    private int endIndex;//结束索引
    public Block() {
    }
    public Block(int min, int max, int startIndex, int endIndex) {
        this.min = min;
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }
    public int getMax() {
        return max;
    }
    public void setMax(int max) {
        this.max = max;
    }
    public int getStartIndex() {
        return startIndex;
    }
    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }
    public int getEndIndex() {
        return endIndex;
    }
    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }
    public String toString() {
        return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
    }
    public int getMin() {
        return min;
    }
    public void setMin(int min) {
        this.min = min;
    }

标签：int,max,常见,number,mid,算法,public,Block
From： https://www.cnblogs.com/kuangshihe/p/16592197.html

常见算法