21、API（算法，lambda表達式，練習）

1、常見的七種查找算法：

? 數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存儲的方式，算法是數(shù)據(jù)計算的方式。

1. 基本查找

? 也叫做順序查找

? 說明：順序查找適合于存儲結(jié)構(gòu)為數(shù)組或者鏈表。

基本思想

基本思想：順序查找也稱為線形查找，屬于無序查找算法。從數(shù)據(jù)結(jié)構(gòu)線的一端開始，順序掃描，依次將遍歷到的結(jié)點與要查找的值相比較，若相等則表示查找成功；若遍歷結(jié)束仍沒有找到相同的，表示查找失敗。

示例代碼：

public class A01_BasicSearchDemo1 {
   
    public static void main(String[] args) {
   
        //基本查找/順序查找
        //核心：
        //從0索引開始挨個往后查找

        //需求：定義一個方法利用基本查找，查詢某個元素是否存在
        //數(shù)據(jù)如下：{131, 127, 147, 81, 103, 23, 7, 79}


        int[] arr = {
   131, 127, 147, 81, 103, 23, 7, 79};
        int number = 82;
        System.out.println(basicSearch(arr, number));

    }

    //參數(shù)：
    //一：數(shù)組
    //二：要查找的元素

    //返回值：
    //元素是否存在
    public static boolean basicSearch(int[] arr, int number){
   
        //利用基本查找來查找number在數(shù)組中是否存在
        for (int i = 0; i < arr.length; i++) {
   
            if(arr[i] == number){
   
                return true;
            }
        }
        return false;
    }
}

public class A01_BasicSearchDemo2 {
   
    public static void main(String[] args) {
   
        System.out.println("課堂練習1:");
        //課堂練習1：
        //需求：定義一個方法利用基本查找，查詢某個元素在數(shù)組中的索引
        //需求：不需要考慮數(shù)組中元素是否重復
        int[] arr = {
   131, 127, 147, 81, 103, 23, 7, 79};
        int num = 81;
        ArrayList list = basicSearch(arr, num);
        printArrayList(arr, list);

        System.out.println("課堂練習2:");
        //課堂練習2：
        //需求：定義一個方法利用基本查找，查詢某個元素在數(shù)組中的索引
        //需求：需要考慮數(shù)組中元素有重復的可能性
        //{131, 127, 147, 81, 103, 23, 7, 79 , 81};
        //我要查找81，想要返回的是所有索引 3 8
        int[] arr2 = {
   131, 127, 147, 81, 103, 23, 7, 79, 81};
        ArrayList list2 = basicSearch(arr2, num);
        printArrayList(arr2, list2);
    }

    /**
     * 打印查找元素所在位置
     * @param arr 數(shù)組
     * @param list 集合
     */
    private static void printArrayList(int[] arr, ArrayList list) {
   
        for (int i = 0; i < list.size(); i++) {
   
            int index = (int) list.get(i);
            System.out.println("arr[" + index + "] = " + arr[index]);
        }
    }

    /**
     * 心得：如果我們要返回多個數(shù)據(jù)的話，可以把這些數(shù)據(jù)放到數(shù)組或者集合中。
     * @param arr 數(shù)組
     * @param number 要查找的元素
     * @return 返回索引的集合
     */
    public static ArrayList basicSearch(int[] arr, int number) {
   
        ArrayList<Integer> list = new ArrayList<>();
        //利用基本查找來查找number在數(shù)組中的位置
        for (int i = 0; i < arr.length; i++) {
   
            if (arr[i] == number) {
   
                list.add(i);
            }
        }
        return list;
    }
}

2. 二分查找

? 也叫做折半查找

說明：元素必須是有序的，從小到大，或者從大到小都是可以的。

如果是無序的，也可以先進行排序。但是排序之后，會改變原有數(shù)據(jù)的順序，查找出來元素位置跟原來的元素可能是不一樣的，所以排序之后再查找只能判斷當前數(shù)據(jù)是否在容器當中，返回的索引無實際的意義。

基本思想

基本思想：也稱為是折半查找，屬于有序查找算法。用給定值先與中間結(jié)點比較。比較完之后有三種情況：

• 相等

  說明找到了

• 要查找的數(shù)據(jù)比中間節(jié)點小

  說明要查找的數(shù)字在中間節(jié)點左邊

• 要查找的數(shù)據(jù)比中間節(jié)點大

  說明要查找的數(shù)字在中間節(jié)點右邊

  案例演示

代碼示例：

public class A02_BinarySearchDemo1 {
   
    public static void main(String[] args) {
   
        //二分查找/折半查找
        //核心：
        //每次排除一半的查找范圍

        //需求：定義一個方法利用二分查找，查詢某個元素在數(shù)組中的索引
        //數(shù)據(jù)如下：{7, 23, 79, 81, 103, 127, 131, 147}

        int[] arr = {
   7, 23, 79, 81, 103, 127, 131, 147};
        System.out.println(binarySearch(arr, 150));
    }

    public static int binarySearch(int[] arr, int number){
   
        //1.定義兩個變量記錄要查找的范圍
        int min = 0;
        int max = arr.length - 1;

        //2.利用循環(huán)不斷的去找要查找的數(shù)據(jù)
        while(true){
   
            if(min > max){
   
                return -1;
            }
            //3.找到min和max的中間位置
            int mid = (min + max) / 2;
            //4.拿著mid指向的元素跟要查找的元素進行比較
            if(arr[mid] > number){
   
                //4.1 number在mid的左邊
                //min不變，max = mid - 1；
                max = mid - 1;
            }else if(arr[mid] < number){
   
                //4.2 number在mid的右邊
                //max不變，min = mid + 1;
                min = mid + 1;
            }else{
   
                //4.3 number跟mid指向的元素一樣
                //找到了
                return mid;
            }

        }
    }
}

總結(jié)

二分查找改進

3. 插值查找

在介紹插值查找之前，先考慮一個問題：

? 為什么二分查找算法一定要是折半，而不是折四分之一或者折更多呢？

其實就是因為方便，簡單，但是如果我能在二分查找的基礎(chǔ)上，讓中間的mid點，盡可能靠近想要查找的元素，那不就能提高查找的效率了嗎？

二分查找中查找點計算如下：

mid=(low+high)/2, 即mid=low+1/2*(high-low);

我們可以將查找的點改進為如下：

mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，

這樣，讓mid值的變化更靠近關(guān)鍵字key，這樣也就間接地減少了比較次數(shù)。

基本思想：基于二分查找算法，將查找點的選擇改進為自適應選擇，可以提高查找效率。當然，差值查找也屬于有序查找。

細節(jié)：對于表長較大，而關(guān)鍵字分布又比較均勻的查找表來說，插值查找算法的平均性能比折半查找要好的多。反之，數(shù)組中如果分布非常不均勻，那么插值查找未必是很合適的選擇。

代碼跟二分查找類似，只要修改一下mid的計算方式即可。

4. 斐波那契查找

在介紹斐波那契查找算法之前，我們先介紹一下很它緊密相連并且大家都熟知的一個概念——黃金分割。

黃金比例又稱黃金分割，是指事物各部分間一定的數(shù)學比例關(guān)系，即將整體一分為二，較大部分與較小部分之比等于整體與較大部分之比，其比值約為1:0.618或1.618:1。

0.618被公認為最具有審美意義的比例數(shù)字，這個數(shù)值的作用不僅僅體現(xiàn)在諸如繪畫、雕塑、音樂、建筑等藝術(shù)領(lǐng)域，而且在管理、工程設(shè)計等方面也有著不可忽視的作用。因此被稱為黃金分割。

在數(shù)學中有一個非常有名的數(shù)學規(guī)律：斐波那契數(shù)列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….

（從第三個數(shù)開始，后邊每一個數(shù)都是前兩個數(shù)的和）。

然后我們會發(fā)現(xiàn)，隨著斐波那契數(shù)列的遞增，前后兩個數(shù)的比值會越來越接近0.618，利用這個特性，我們就可以將黃金比例運用到查找技術(shù)中。

基本思想：也是二分查找的一種提升算法，通過運用黃金比例的概念在數(shù)列中選擇查找點進行查找，提高查找效率。同樣地，斐波那契查找也屬于一種有序查找算法。

斐波那契查找也是在二分查找的基礎(chǔ)上進行了優(yōu)化，優(yōu)化中間點mid的計算方式即可

代碼示例：

public class FeiBoSearchDemo {
   
    public static int maxSize = 20;

    public static void main(String[] args) {
   
        int[] arr = {
   1, 8, 10, 89, 1000, 1234};
        System.out.println(search(arr, 1234));
    }

    public static int[] getFeiBo() {
   
        int[] arr = new int[maxSize];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < maxSize; i++) {
   
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr;
    }

    public static int search(int[] arr, int key) {
   
        int low = 0;
        int high = arr.length - 1;
        //表示斐波那契數(shù)分割數(shù)的下標值
        int index = 0;
        int mid = 0;
        //調(diào)用斐波那契數(shù)列
        int[] f = getFeiBo();
        //獲取斐波那契分割數(shù)值的下標
        while (high > (f[index] - 1)) {
   
            index++;
        }
        //因為f[k]值可能大于a的長度，因此需要使用Arrays工具類，構(gòu)造一個新法數(shù)組，并指向temp[],不足的部分會使用0補齊
        int[] temp = Arrays.copyOf(arr, f[index]);
        //實際需要使用arr數(shù)組的最后一個數(shù)來填充不足的部分
        for (int i = high + 1; i < temp.length; i++) {
   
            temp[i] = arr[high];
        }
        //使用while循環(huán)處理，找到key值
        while (low <= high) {
   
            mid = low + f[index - 1] - 1;
            if (key < temp[mid]) {
   //向數(shù)組的前面部分進行查找
                high = mid - 1;
                /*
                  對k--進行理解
                  1.全部元素=前面的元素+后面的元素
                  2.f[k]=k[k-1]+f[k-2]
                  因為前面有k-1個元素沒所以可以繼續(xù)分為f[k-1]=f[k-2]+f[k-3]
                  即在f[k-1]的前面繼續(xù)查找k--
                  即下次循環(huán),mid=f[k-1-1]-1
                 */
                index--;
            } else if (key > temp[mid]) {
   //向數(shù)組的后面的部分進行查找
                low = mid + 1;
                index -= 2;
            } else {
   //找到了
                //需要確定返回的是哪個下標
                if (mid <= high) {
   
                    return mid;
                } else {
   
                    return high;
                }
            }
        }
        return -1;
    }
}

5. 分塊查找

當數(shù)據(jù)表中的數(shù)據(jù)元素很多時，可以采用分塊查找。

汲取了順序查找和折半查找各自的優(yōu)點，既有動態(tài)結(jié)構(gòu)，又適于快速查找

分塊查找適用于數(shù)據(jù)較多，但是數(shù)據(jù)不會發(fā)生變化的情況，如果需要一邊添加一邊查找，建議使用哈希查找文章來源地址http://www.zghlxwxcb.cn/news/detail-453760.html

分塊查找的過程：

1. 需要把數(shù)據(jù)分成N多小塊，塊與塊之間不能有數(shù)據(jù)重復的交集。
2. 給每一塊創(chuàng)建對象單獨存儲到數(shù)組當中
3. 查找數(shù)據(jù)的時候，先在數(shù)組查，當前數(shù)據(jù)屬于哪一塊
4. 再到這一塊中順序查找

代碼示例：

public class A03_BlockSearchDemo1 {
   
    public static void main(String[] args) {
   
        /*
            分塊查找
            核心思想：
                塊內(nèi)無序，塊間有序
            實現(xiàn)步驟：
                1.創(chuàng)建數(shù)組blockArr存放每一個塊對象的信息
                2.先查找blockArr確定要查找的數(shù)據(jù)屬于哪一塊
                3.再單獨遍歷這一塊數(shù)據(jù)即可
        */
        int[] arr = {
   16, 5, 9, 12, 21, 18,
                32, 23, 37, 26, 45, 34,
                50, 48, 61, 52, 73, 66};

        //1.要把數(shù)據(jù)進行分塊
        //要分為幾塊: 18 開根號 4.24塊
        //18 / 4 = 4.5個
        //System.out.println("arr.length = " + arr.length);
        //System.out.println("Math.sqrt(arr.length) = " + Math.sqrt(arr.length));

        //創(chuàng)建三個塊的對象
        Block b1 = new Block(21, 0, 5);
        Block b2 = new Block(45, 6, 11);
        Block b3 = new Block(73, 12, 17);

        //定義數(shù)組用來管理三個塊的對象（索引表）
        Block[] blockArr 

到了這里，關(guān)于java基礎(chǔ)入門-12-【API（算法，lambda表達式，練習）】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！