Java 数据结构与算法-EW帮帮网

package com.algorithm;

public class BasicSearch {
    public static void main(String[] args) {
        // 基本查找
        // 从 0 索引开始挨个往后查找
        // 需求：定义一个方法利用基本查找，查询某个元素是否存在
        int[] arr = {131, 127, 147, 81, 103, 23, 7, 79, 81};
        int number = 131;
        System.out.println(basicSearch(arr, number));
    }

    // 查找
    public static boolean basicSearch(int[] arr, int number) {
        // 利用基本查找来查找 number 在数组中是否存在
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == number) {
                return true;
            }
        }
        return false;

2 二分查找/折半查找

2.1 条件

2.1.1 需求

在有序数组 A 内，查找值 target，如果找到返回索引，如果找不到返回 -1。

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

核心逻辑：每次排除一般的查找范围

2.1.2 描述

(1) 给定包含 n 个元素的有序数组 A，满足 $A_{0}\leqslant A_{1}\leqslant A_{2}\leqslant ...\leqslant A_{n-1}$ ，一个待查值 target

(2) 设置 i = 0，j = n -1

(3) 如果 i > j ，结束查找，没找到

(4) 设置 $m=floor(\frac{I+j}{2})$ ，m 为中间索引，floor 是向下取整（ $\leq \frac{i+j}{2}$ ）的最小整数

(5) 如果 $target < A_{m}$ 设置 j = m - 1，跳到第 2 步

(6) 如果 $A_{m} < target$ 设置 i = m + 1，跳到第 2 步

(7) 如果 $A_{m} = target$ ，结束查找，找到了

2.2 说明

2.2.1 指针和中间值

(1) min 和 max 表示当前要查找的范围

(2) mid 是在 min 和 max 中间的

(3) 如果要查找的元素在 min 的右边，缩小范围时，min 不变，max 等于 mid 减 1

(4) 如果要查找的元素在 mid 的右边，缩小范围时，max 不变，min 等于 mid 加 1

2.2.2 代码说明

package com.algorithm.demo;

public class BinarySearchBasic {
    public static int binarySearch(int[] a, int target) {
        int i = 0, j = a.length - 1; // 设置指针和初值
        while (i <= j) { // 指针相遇时结束循环
            int m = (j + i) >>> 1; // 计算中间指针 java 会自动取整

            if (target < a[m]) { // 目标在左边
                j = m - 1;
            } else if (target > a[m]) { // 目标在右边
                i = m + 1;
            } else if (a[m] < target) {
                i = m + 1; // 目标元素在右边
            } else {
                return m; // 找到目标元素
            }
        }
        return -1;
    }
}

假设有一个有序数组 a，数组 a 的大小/长度为 length，需查找的值为 target，定义指针 i、j，初值分别为 0、length - 1，如下图所示。当 i <= j 时，即 i 在 j 的左侧，表示 i ~ j 这个范围内有数据，可以进行 while 循环，当 i > j 时，即 i 在 j 的右侧，表示没有找到，返回 -1。while 循环中，定义 m 取 i ~ j 的中间位置，java 默认向下取整，即 $\left \lfloor x \right \rfloor$ ，取不超过 x 的最大整数，而这里运用了无符号右移“<<<”，移动1位，如： $i=2,j=7,\frac{j}{i} = \frac{7}{2}=3;i=3,j=10,\frac{j}{i}=\frac{10}{3}=3;...$

如果要查找的值 target 小于中间值 a[m]，就让 j 取 m - 1，表示目标值在 m 的左侧；如果目标值 target 大于中间值 a[m]，就让 i 取 m + 1，表示目标值在 m 的右侧；如果目标值 target 等于 a[m]，表示 m 索引的值 a[m] 就是要找的目标值 target 。

2.3 比较

2.3.1 执行次数

2.3.1.1 线形查找

package com.algorithm.demo;

/**
 * 线性查找
 * Params:
 * a - 待查找的升序数组（可以不是有序数组）
 * target - 待查找的目标值
 *
 * Returns:
 * 找到：目标值在数组中的索引
 * 未找到：如果未找到则返回 -1
 */

public class LinearSearch {
    public static int LinarSearch(int[] a, int target) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

假设数据元素个数 n，首先，int i = 0 执行 1 次；其次，i < a.length 为 n + 1 次，因为从 0 到 n - 1 比较 n 次，第 n 次比较后不符退出循环，所以是 n + 1 次；然后，i ++ 执行 n 次；最后，a[ i ] == target 执行 n 次，若循环完毕还没有找到，则 return i 不执行，那么执行 renturn -1 1 次。综上所述，这个代码总共执行 1 + ( n + 1 ) + n + n + 1 = 3 * n + 3 次。

2.3.1.2 二分查找

package com.algorithm.demo;

public class BinarySearchBasic {
    
    /*二分查找
      Params a 待查找的升序数组
            target 待查找的目标值
      Returns 找到则返回索引，找不到返回 -1   
    */
    public static int binarySearch(int[] a, int target) {
        int i = 0, j = a.length - 1; // 设置指针和初值
        while (i <= j) { // 指针相遇时结束循环
            int m = (j + i) >>> 1; // 计算中间指针 java 会自动取整

            if (target < a[m]) { // 目标在左边
                j = m - 1;
            } else if (target > a[m]) { // 目标在右边
                i = m + 1;
            } else if (a[m] < target) {
                i = m + 1; // 目标元素在右边
            } else {
                return m; // 找到目标元素
            }
        }
        return -1;
    }
}

假设一个有序数组 a[]，n 为数组长度（元素个数），目标值 target，首先，int i = 0 执行 1 次，j = a.length - 1 执行 1 次，没找到的话，return -1 要执行 1 次；其次，中间的 while 循环一共执行 $L=floor(log_{2}n)+1$ 次。所以，i <= j 执行 L+1 次，int m=(i+j)>>>1 执行L次，target < a[m]执行L次，a[m] < target执行L次；然后，因为目标值target很大，找不到，一直会往右边找，所以i=m+1的执行次数为L次；最后，二分查找的总次数为 $(floor(log_{2}n)+1) * 5 + 4$

2.3.2 总结

2.3.2.1 二分查找

(1) 若数组元素个数在这个区间内 $a.length\in [4, 7]\in Z^{+}$ ，则循环次数为3，即： $floor(log_2(4))+1=2+1=3$

(2) 若数组元素个数在这个区间内 $a.length\in [8,15]\in Z^{+}$ ，则循环次数为4，即： $floor(log_2(8))+1=3+1=4$

(3) 若数组元素个数在这个区间内 $a.length\in [16,31]\in Z^{+}$ ，则循环次数为5，即： $floor(log_2(16))+1=4+1=5$

(4) 若数组元素个数在这个区间内 $a.length\in [32,63]\in Z^{+}$ ，则循环次数为6，即： $floor(log_2(32))+1=5+1=6$

(5) ......

(6) 若数组元素个数在这个区间内 $n = a.length\in [2^{k},2^{k+1}-1]\in Z^{+},k \in Z^{+}$ ，则循环次数为 $floor(log_2(n))+1=floor(log_22^{k})+1=floor(k)+1$ ，其中： $floor(log_2(2^{k}))$ 为 $log_{2}2^{k}$ 向下取整.

2.3.2.2 线形查找

代码总共执行 1 + ( n + 1 ) + n + n + 1 = 3 * n + 3 次

2.3.2.3 时间衡量

设每行语句执行时间一样，均为t，数据元素个数a.length=n，则

(1) 二分查找执行的总时间为： $T_{BinarySearch}=((floor(log_{2}n)+1)*5+1)*t$

(2) 线形查找执行的总时间为： $T_{LinearSearch}=(1 + ( n + 1 ) + n + n + 1)*t= (3 * n + 3)*t$

(3) 函数 $f(x)=log_2(x)+1,g(x)=3x+3$ 图像对比：

当 x 很小时，如下图：

当 x 很大时，如下图：

注明：Windows 画图网站：https://www.desmos.com/calculator?lang=zh-CN https://www.desmos.com/calculator?lang=zh-CN

2.3.3 重复元素查找

2.3.3.1 基础版

public class BinarySearchBasic {
    public static int binarySearch(int[] a, int target) {
        int i = 0, j = a.length - 1; // 设置指针和初值
        while (i <= j) { // 指针相遇时结束循环
            int m = (j + i)  >>> 1;// 计算中间指针 java 会自动取整

            if (target < a[m]) { // 目标在左边
                j = m - 1;
            } else if (target > a[m]) { // 目标在右边
                i = m + 1;
            } else if (a[m] < target) {
                i = m + 1; // 目标元素在右边
            } else {
                return m; // 找到目标元素
            }
        }
        return -1;
    }
}

从上图可以看出，二分查找-基础版代码如果说出现重复元素，返回的是第一个重复元素的下标，从而忽视了后面的重复元素，同时这也是碰巧返回了最左侧的重复元素，再看看下面。

图2 就不是返回最左侧的重复元素，如果说我需要写的代码能返回最左侧的重复元素，看下面！

2.3.3.1 Left most

2.3.3.1.1 基础版

package com.algorithm.demo;

public class LeftMost {
    public static int leftMost(int[] a, int target) {
        int i = 0, j = a.length - 1; // 设置指针和初值
        int candidate = -1; // 初始化候选索引为 -1
        while (i <= j) { // 指针相遇时结束循环
            int m = (j + i)  >>> 1;// 计算中间指针 java 会自动取整
            if (target < a[m]) { // 目标在左边
                j = m - 1;
            } else if (a[m] < target) { // 目标在右边
                i = m + 1;
            } else if (a[m] < target) {
                i = m + 1; // 目标元素在右边
            } else {
                // 记录候选位置
                candidate = m;
                j = m - 1; // 继续向左查找
            }
        }
        return candidate;
    }
}

2.3.3.1.2 改进版

package com.algorithm.structure;
/**
 * Params: a - 待查找的升序数组
 *         target - 待查找的目标值
 *
 * Returns:
 *         找到则返回最靠左索引
 *         找不到返回 -1
 *         返回 >= target 的最靠左索引
 * */
public class LeftMostPlus {
    public static int search(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target <= a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i;
    }
}

2.3.3.2 High most

2.3.3.2.1 基础版

package com.algorithm.structure;

/**
 * 二分查找 RightMost
 *
 * Params: a - 待查找的升序数组
 *         target - 待查找的目标值
 *
 * Returns:
 *         找到则返回最靠右索引
 *         找不到返回 -1
 * */
public class RightMost {
    public static int binarySearchRightmost(int[] a, int target) {
        int i = 0, j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                candidate = m;
                i = m + 1;
            }
        }
        return candidate;
    }
}

2.3.3.2.2 改进版

package com.algorithm.structure;
/**
 * Params: a - 待查找的升序数组
 *         target - 待查找的目标值
 *
 * Returns:
 *         返回 <= target 的最靠右索引
 */

public class RightMostPlus {
    public static int binarySearchRightmostPlus(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i - 1;
    }
}

2.4 时间复杂度

计算机科学中，时间复杂度是用来衡量：一个算法的执行，随数据规模增大，而增长的时间成本。

2.4.1 说明

假设算法处理的数据规模是 n，代码总的执行行数用函数 f(n) 来表示，例如，

(1) 线形查找算法的函数： $f(n)=3*n+3$

(2) 二分查找算法的函数： $f(n) = (floor(log_{2}n)+1)*5+4$

为了对 f(n) 进行化简，应当抓住主要矛盾，找到一个变化趋势与之相近的表示法。

(1) $c,c_{1},c_{2}$ 都为一个常数

(2) f(n) 是实际执行代码行数与 n 的函数

(3) g(n) 是经过化简，变化趋势与 f(n) 一致的 n 的函数

2.4.2 分类

2.4.2.1 asymptotic upper bound

渐进上界：从某个常数 $n_{0}$ 开始， $c*g(n)$ 总是位于 $f(n)$ 上方，那么计作 $O(g(n))$

注明：代表算法执行的最差情况！

例如， $f(n)=n^{2}+100$ ，从 $n_{0}=10$ 时， $g(n)=2 * n^{2}$ 是它渐进上界，计作 $O(n^{2})$

2.4.2.2 asymptotic lower bound

渐进下界：从某个常熟 $n_{0}$ 开始， $c*g(n)$ 总是位于 $f(n)$ 下方，那么计作 $\Omega (g(n))$

2.4.2.3 asymptotic tight bounds

渐进紧界：从某个常数 $n_{0}$ 开始， $f(n)$ 总是在 $c_{1} * g(n)$ 和 $c_{2}*g(n)$ 之间，那么计作 $\Theta (g(n))$

2.4.3 实例

渐进上界：从某个常数 $n_{0}$ 开始， $c*g(n)$ 总是位于 $f(n)$ 上方，那么计作 $O(g(n))$

(1) $f(x)=3*n+3,g(n)=n$ ，取c=4，在 $n_{0}=3$ 之后，g(n)可以作为f(n)的渐进上界，因此表示法写作 O(n)

渐进下界：从某个常熟 $n_{0}$ 开始， $c*g(n)$ 总是位于 $f(n)$ 下方，那么计作 $\Omega (g(n))$

(2) $f(n)=(floor(log_2(n))+1)*5+4=5*floor(log_2(n))+9=5\left \lfloor log_{2}(n) \right \rfloor +9$

$g(x)=log_2(n)$

$g(n)=3*log_{2}n$

$g(n)=10*log_{2}n$

注明：f(n) 的渐进上界为 $f(n)=O(g(n))$

已知f(n)来说，求g(n)

(1) 表达式中相乘的常量，可以省略，如： $f(n)=100*n^{2}$ 中的100，即： $g(n)=n^{2}$

(2) 多项式中数量规模更小（低次项）的表达式，如：

$f(n)=n^{2}+n$ 中的 $n$ 可以省略，即： $g(n)=n^{2}$

$f(n) =n^{3}+n^{2}$ 中的 $n^{2}$ 可以省略，即： $g(n)=n^{3}$

(3) 不同底数的对数，渐进上界可以用一个对数函数 log n 表示

例如， $log_{2}n$ 可以替换为 $log_{10}(n)$ ，因为 $log_{2}(n)=\frac{log_{10}(n)}{log_{10}(2)}$ ，相乘的常量 $\frac{1}{log_{10}(2)}$ 可以省略

(4) 类似的，对数的常数次幂可以省略，如： $log(n^{c})=c*log(n)$

2.4.4 常见的大O表示法

按时间复杂度从低到高：

(1) 红色横线：O(1) 常量时间，意味着算法时间并不随着数据规模而变化

(2) 绿色： $O(log(n))$ 对数时间

(3) 黄色：O(n) 线性时间，算法时间与数据规模成正比

(4) 蓝色： $O(n*log(n))$ 拟线性时间

(5) 紫色： $O(n^{2})$ 平方时间

(6) 粉色朝上： $O(2^{n})$ 指数时间

(7) 黑色：O(n!)

2.5 空间复杂度

有时间复杂度类似，一般也使用大 O 表示法来衡量：一个算法执行随数据规模增大，而增大的额外空间成本

package com.algorithm.demo;

public class BinarySearchBasic {
    public static int binarySearch(int[] a, int target) {
        int i = 0, j = a.length - 1; // 设置指针和初值
        while (i <= j) { // 指针相遇时结束循环
            int m = (j + i)  >>> 1;// 计算中间指针 java 会自动取整

            if (target < a[m]) { // 目标在左边
                j = m - 1;
            } else if (target > a[m]) { // 目标在右边
                i = m + 1;
            } else if (a[m] < target) {
                i = m + 1; // 目标元素在右边
            } else {
                return m; // 找到目标元素
            }
        }
        return -1;
    }
}

对于空间复杂度，首先，指针 i 占用了 4 个字节，其次，指针 j 占用了 4 个字节，然后，指针 m 占用了 4 个字节，一共占用了 12 个字节。

(1) 左闭右开的区间，i 指向的可能是目标，而 j 指向的不是目标

(2) 不在循环内找出，等范围内只剩 i 时，退出循环，在循环外比较 a[i] 与 target

(3) 循环内的平均比较次数减少了

(4) 时间复杂度 $\Theta (log(n))$

2.6 二分查找性能

下面分析二分查找算法的性能

(1) 时间复杂度

最坏情况 O(log n)

最好情况：如果待查找元素恰好在数组中央，只需要循环一次 O(1)

(2) 空间复杂度

需要常数个指针 i, j, m，因此额外占用的空间是 O(1)

2.4 代码

package com.algorithm;

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

        // 需求：定义一个方法利用二分查找，查询某个元素在数组中的索引
        int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
        int index = binarySearch(arr, 81);
        System.out.println(index);
    }
    
    public static int binarySearch(int[] arr, int number) {
        // 1 定义两个变量，记录要查找的范围
        int min = 0;
        int max = arr.length - 1;
        
        // 2 利用循环不断的去找要查找的数据
        while(true) {
            if (min > max) {
                return -1;
            }
            
            // 3 找到 min 和 max 的中间位置
            int mid = (min + max) / 2;
            
            // 4 拿着 mid 指向的元素跟要查找的元素进行比较
            // 4.1 number 在 mid 的左边
            // 4.2 number 在 mid 的右边
            // 4.3 number 跟 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;
            }
        }
    }
}

2.5 总结

2.4.1 二分查找的优势

提前查找效率

2.4.2 二分查找的前提条件

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

2.4.3 二分查找的过程

(1) min 和 max 表示当前要查找的范围

(2) mid 是在 min 和 max 中间的

(3) 如果要查找的元素在 mid 的左边，缩小范围时，min 不变，max 等于 mid 减 1

(4) 如果要查找的元素在 mid 的右边，缩小范围时，max 不变，min 等于 mid 加 1

3 插值查找

4 斐波拉契查找

注明：斐波拉契查找属于二分查找的改进。

1 : 0.618 -------------------> mid = min + 黄金分割点左半边长度 - 1

5 总结

(1) 二分查找、插值查找，斐波拉契查询各自的特点，相同点：都是通过不断的缩小范围来查找对应的数据的；不同点：计算 mid 的方式不一样。

(2) 二分查找：mid 每次都是指向范围的中间位置。

(3) 插值查找：mid 尽可能的靠近要查找的数据，但是要求数据尽可能的分布均匀。

(4) 斐波拉契查找：根据黄金分割点来计算 mid 指向的位置。

6 分块查找

6.1 原则

6.1.1 原则 1

前一块中的最大数据，小于后一块中所有的数据（块内无序，块间有序）。

6.1.2 原则 2

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

6.1.3 核心思路

先确定要查找的元素在哪一块，然后块内挨个查找。

7 其他查找

7.1 数表查找

7.2 哈希查找

8 数组

8.1 定义

数组是由一组元素（值或变量）组成的数据结构，每个元素有至少一个索引或键来标识。

因为数组内的元素是连续存储的，所以数组中元素的地址，可以通过其索引计算出来，例如：

因为数据类型 int 占用 4 个字节，所以元素 1 的地址为 b，元素 2 的地址为 b+4，元素 3 的地址为 b+12，...

知道数组的数据起始位置 Base Address，就可以由 BaseAddress + i * size 计算出索引 i 元素的地址，i 即索引，在 java、C 语言都是从 0 开始，size 是每个元素占用字节，例如 int 占用 4，double 占用 8。

8.2 动态数组

8.2.1 插入

package com.algorithm.structure;

// 动态数组
public class DynamicArray { ;
    private int size = 0; // 逻辑大小
    private int capacity = 8; // 容量
    private int[] array = new int[capacity]; // 底层数组

    public void addLast(int element) {

        // 1. 插入元素
        array[size] = element;
        size++;
    }

    public void add(int index, int element) {
        if(index >= 0 && index < size) {
            // 接收的第一个参数是数组是谁（array），第二个参数是从哪个位置开始拷贝，第三个参数是在哪个数组内进行拷贝，第四个参数是拷贝到数组的哪个位置，第五个参数是拷贝的长度（要拷贝几个元素）
            System.arraycopy(array, index, array, index + 1, size - index);
            array[index] = element;
            size++;
        }

        array[index] = element;
        size++;
    }
}

8.2.1.1 类 DynamicArray

在类 DynamicArray 中，定义 size 为数组 array 的逻辑大小，可以理解为元素下标；定义 capacity 为数组 array 的容量，即数组最多能够存储多少个数据元素。

8.2.1.2 方法 addLast

在方法 addLast 中，形参 element 为数组 array 赋值，赋完值后 +1。

8.2.1.3 方法 add

插入新元素：在方法 add 中，形参 index 表示要插入的新元素的索引位置，形参 element 表示要插入的值。假设 index = 2，即要在索引（下标）为 2 的位置上插入新元素，则需要将从索引为3开始的所有元素向后移动 1 位，通过 System.arraycopy( ) 实现数组间或数组内的拷贝复制。

下面讨论 System.arraycopy( ) 的括号内形参表示的内容：

/** 接收的第一个参数是数组是谁（array），第二个参数是从哪个位置开始拷贝，第三个参数是在哪个数组内进行拷贝，第四个参数是拷贝到数组的哪个位置，第五个参数是拷贝的长度（要拷贝几个元素）
*/
System.arraycopy(array, index, array, index + 1, size - index);

(1) array 接收的第一个参数就是“数组是谁”，就是这个数组 array；

(2) index 接收的第二个参数就是“从哪个位置开始拷贝”，就是从 index 开始拷贝；

(3) array 接收的第三个参数就是“要拷贝到的目标数组”，就是 array；

(4) index + 1 接收的第四个参数就是“目标数组的起始位置”，就是 index + 1；

(5) size - index 接收的第五个参数就是“拷贝的元素个数”，就是 size - index。

上面代码的含义：从原始数组 array 的索引（下标）为 index 开始进行拷贝，拷贝到同一个数组 array 的后移动 1 位的位置，即拷贝到 index + 1 的位置，拷贝 size - index 个元素。

拷贝完成后，index = 2 的索引位置空出，通过 array[ index ] 定位到索引为 index = 2 的位置，赋值 array[ index ] = element，同时 size 也要向后移动 1 位，即 size ++ 等价于 size = size + 1。

插入的整体代码可以改成如下：

package com.algorithm.structure;

// 动态数组
public class DynamicArray { ;
    private int size = 0; // 逻辑大小
    private int capacity = 8; // 容量
    private int[] array = new int[capacity]; // 底层数组

    public void addLast(int element) {

        add(size, element);
    }

    public void add(int index, int element) {
        if(index >= 0 && index < size) {
            // 接收的第一个参数是数组是谁（array），第二个参数是从哪个位置开始拷贝，第三个参数是在哪个数组内进行拷贝，第四个参数是拷贝到数组的哪个位置，第五个参数是拷贝的长度（要拷贝几个元素）
            System.arraycopy(array, index, array, index + 1, size - index);
        }
        array[index] = element;
        size++;
    }
}

8.2.2 遍历

package com.algorithm.structure;

import java.util.function.Consumer;

// 动态数组
public class DynamicArray { ;
    private int size = 0; // 逻辑大小
    private int capacity = 8; // 容量
    private int[] array = new int[capacity]; // 底层数组

    /*
     * 向最后位置 [size] 添加元素
     * Params: element - 待添加的元素
     */
    public void addLast(int element) {
        
        /*
        // 1. 插入元素
        array[size] = element;
        size++;
        */
        add(size, element);
    }

    /*
    * 向 [0 .. size] 位置添加元素\
    * Params: index - 索引位置
    *         element - 待添加的元素
    */
    public void add(int index, int element) {
        if(index >= 0 && index < size) {
            // 接收的第一个参数是数组是谁（array），第二个参数是从哪个位置开始拷贝，第三个参数是在哪个数组内进行拷贝，第四个参数是拷贝到数组的哪个位置，第五个参数是拷贝的长度（要拷贝几个元素）
            System.arraycopy(array, index, array, index + 1, size - index);
        }
        array[index] = element;
        size++;
    }

    /*
     * 查询元素
     * Params: index - 索引位置，在 [0 ... size) 区间内
     * Returns: 该索引位置的元素
     */
    public int get(int index) { // [0 ... size]
            return array[index];
    }

    /*
     * 遍历方法 1
     * Params: consumer - 遍历要执行的操作，入参：每个元素
     */
    public void forEach(Consumer<Integer> consumer) {
        for(int i = 0; i < size; i++) {
            // System.out.println(array[i]);
            // 提供 array[i]
            // 返回 void
            consumer.accept(array[i]);
        }
    }
}

Java 数据结构与算法

1 基本查找