数据结构之数组（附带二分法查询）

た入场券 2023-02-10 03:56 61阅读 0赞

## 一、数组的简要 ##

Java数组对象的类是一种特殊的类，在Java内部是没有这个类的，数组对象的类是在运行时确立的，没有生命任何成员变量、成员方法、构造函数、Annotation甚至连length成员变量这都没有，它就是一个彻彻底底的空类。

对数组对象取长度的时候，需用到.length，而不是一般对象的.length()，是因为JVM在处理时对数组的长度做了特殊的处理，它是通过arraylength这条指令来实现的。

数组的典型使用案例: ArrayList 就是基于数组实现的

### 1、Java数组的默认初始化值 ###

a.基本数据类型byte,short,int,long，默认的初始化值为0;
    
       b.基本数据类型float，double的默认初始值为0.0
    
       c.基本数据类型char的默认初始值为:\0000
    
       d.基本引用类型的默认初始值为null

### 2、Java数组初始化的几种方式 ###

1、一种为静态初始化

在创建数组的时候就指定了数组的长度，如下面的内容:
    
        int[] array_static=new int[]{1,2,3};

2、第二种为动态初始化

在创建数组的时候仅仅指定数组的长度
    
        int[] array_dynamic=new int[10];

### 3、数组的底层实现 ###

java 的数组是一个特殊的存在，核心是一段连续的内存，数组的使用分为四个步骤：声明数组、分配空间、赋值、处理。

java中把内存分为了堆内存和栈内存，当初始化数组时，堆内存分配相应大小的连续的内存块，并将第一个内存块的地址放入栈内存中存储。这样读取数据的时候取第0个就是首地址的内存中的数据，第1个就是首地址+1的内存块中数据。其余删除与写入操作与读取类似。

本人见解有限，更多参考：[https://www.cnblogs.com/chenssy/p/3463719.html][https_www.cnblogs.com_chenssy_p_3463719.html]

## 二、数组的基本定义方式( 面向过程) ##

### 1、数组的创建方式一 （直接设置值） ###

long[] arr = new long[]{2, 3, 4};
            
            for (int i = 0; i < arr.length; i++) {
                System.out.println(arr[i]);
            }

### 2、数组的创建方式二 （设置数组长度） ###

long[] arr2 = new long[3];
            arr2[0] = 1;
            arr2[1] = 2;
            arr2[2] = 2;
            for (int i = 0; i < arr.length; i++) {
                System.out.println(arr2[i]);
            }

### 3、数组的创建方式三 （二维数组） ###

long[][] arr3 = new long[2][2];
            arr3[0][0] = 1;
            arr3[0][1] = 2;
            arr3[1][0] = 3;
            arr3[1][1] = 4;
            
            // 打印
            for (int i = 0; i < arr3.length; i++) {
                for (int j = 0; j < arr3[i].length; j++) {
                    System.out.println("arr3[" + i + "][" + j + "] == " + arr3[i][j]);
                }
          }

上面这些就是数组的基本使用了，下面将使用对象来包装数组，使数组获取 **增/删/改/查** 的功能

## 三、定义对象操作数组 ( 面向对象) ##

### 1、创建数组的包装类 ###

1、我们创建一个 Object\[\] arr 来存放任意的数组对象

2、我们创建一个 size 来数组arr 数组对象的长度，当arr 值发生变化时，可动态数组长度，等于扩容机制（此功能本为不演示）

3、 创建构造器，XJArray() 和 XJArray(int size) ，当new 对象的所有可以获取默认长度 或 手动设置长度

4、创建 println() 方法，方便测试和查看当前数组中存在的数据

public class XJArray {
    
        //数组内容
        private Object[] arr;
    
        //数组长度
        private int size;
    
        // new 对象时设置数组默认长度
        public XJArray() {
            arr = new Object[12];
        }
    
        // new 对象时手动数组的长度
        public XJArray(int size) {
            arr = new Object[size];
        }
    
    
        /**
         * TODO 打印数组数据，快速查看当前数组的数据，无实际用处
         */
        public void println() {
            System.out.print("[");
            for (int i = 0; i < size; i++) {
                System.out.print(arr[i] + ",");
            }
            System.out.println("]");
        }
    }

使用数组对象示例

public class XJArrayTest {
    
        public static void main(String[] args) {
            XJArray xjArray = new XJArray();
            XJArray xjArray2 = new XJArray(16);
        }
    }

数组对象创建出来了，那么我们如何实现增删改查呢

### 2、增1 ( 无序） ###

array 数组添加图示例，无序的，传入一个索引+1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1_size_16_color_FFFFFF_t_70]

/**
         * TODO 添加数据
         */
        public void add(Object value) {
            arr[size] = value;
            size++;
        }

测试代码

xjArray.add(1);
      xjArray.add(5);
      xjArray.add(3);
      xjArray.add(2);
      xjArray.println();   //输出  [1,5,3,2,]

### 3、增2 (有序, 销量低） ###

*  1、找到插入的索引位置
 *  2、使用 System.arraycopy 方法移动指定索引的数据位置
 *  3、添加找到的索引位置数据  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1_size_16_color_FFFFFF_t_70 1]  
    添加方法

/**
         * TODO 添加数据(有序的添加)
         */
        public void put(long value) {
            //
            int index = size;
            for (int i = 0; i < size; i++) {
                if (arr[i] >= value) {
                    index = i;
                    break;
                }
            }
            System.arraycopy(arr, index, arr, index + 1, size);
            arr[index] = value;
            size++;
        }

*  System.arraycopy 方法说明,估计很多人没见个这个方法，简单说明一下参数

//   Object src :  原数组
    //   int srcPos :  从元数据的起始位置开始
    //　　Object dest : 目标数组
    //　　int destPos : 目标数组的开始起始位置
    //　　int length  : 要copy的数组的长度

测试代码

XJArray xjArray2 = new XJArray(16);
      xjArray2.put(1);
      xjArray2.put(5);
      xjArray2.put(3);
      xjArray2.put(2);
      xjArray2.put(4);
      xjArray2.println();  // 输出 [1,2,3,4,5,]

### 4、删 ###

*  原理同有序增加，
 *  有序增加是往后移动，
 *  删除是往前移动,
 *  指定删除的索引数据直接被从后移动的数据覆盖  
    \-![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1_size_16_color_FFFFFF_t_70 2]

public void delete(int index) {
            if (index >= size || index < 0) {
                throw new ArrayIndexOutOfBoundsException();
            } else {
                System.arraycopy(arr, index+1, arr, index , size);
                size--;
            }
        }

测试代码

XJArray xjArray2 = new XJArray(16);
      xjArray2.put(1);
      xjArray2.put(5);
      xjArray2.put(3);
      xjArray2.put(2);
      xjArray2.put(4);
      xjArray2.println();  //输出  [1,2,3,4,5,]
    
      xjArray2.delete(0);
      xjArray2.println();  //输出  [2,3,4,5,]
    
      xjArray2.delete(2);
      xjArray2.println();  //输出  [2,3,5,]

### 5、改 ###

改就没什么好说的了，直接在对应的索引重新赋值就好了

public void upd(int index, int newValue) {
            if (index >= size || index < 0) {
                throw new ArrayIndexOutOfBoundsException();
            } else {
                arr[index] = newValue;
            }
        }

### 6、查1 (索引查值–线性查询） ###

线性查询就是普通查询，这个也没什么好说的,根据索引直接获取就好了

public long get(int index) {
            if (index >= size || index < 0) {
                throw new ArrayIndexOutOfBoundsException();
            } else {
                return arr[index];
            }
        }

### 7、查2 (值查索引–二分法查询） ###

二分法查询

*  1、数组必须是有序的
 *  2、每次从中间划开,判断值是在左边还是右边，判断后重复划开在判断  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1_size_16_color_FFFFFF_t_70 3]

/**
         * 二分法查找数据（arr 必须是有序的，否则不可使用）
         */
        public int binarySearch(long value) {
            int start = 0;            // 数组最小索引值
            int end = size;           // 数组最大索引值，长度=数组数据数量时可使用: arr.length - 1;
            while (start <= end) {
                int middle = (start + end) / 2;
                if (value < arr[middle]) {
                    // 值小于中间值,那么值一定在左边
                    end = middle - 1;
                } else if (value > arr[middle]) {
                    // 值大于中间值,那么值一定在右边
                    start = middle + 1;
                } else if (value == arr[middle]) {
                    // 找到了
                    return middle;
                }
            }
            //start>end的情况，这种情况下value的值大于arr中最大的元素值或者value的值小于arr中最小的元素值
            return -1;
        }

测试代码

XJArray xjArray2 = new XJArray(16);
            xjArray2.put(1);
            xjArray2.put(3);
            xjArray2.put(2);
            xjArray2.println();  // [1,2,3,]
            System.out.println("索引位置:"+xjArray2.binarySearch( 1)); // 输出0
            System.out.println("索引位置:"+xjArray2.binarySearch( 2)); // 输出1
            System.out.println("索引位置:"+xjArray2.binarySearch( 3)); // 输出2
            System.out.println("索引位置:"+xjArray2.binarySearch( 4)); // 输出-1

**本文到此结束，如果觉得有用，劳烦各位点赞关注一下呗，将不定时持续更新更多的内容…，感谢大家的观看！**

[https_www.cnblogs.com_chenssy_p_3463719.html]: https://www.cnblogs.com/chenssy/p/3463719.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200520231455593.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200521002424368.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200521002207300.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200521011247121.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1,size_16,color_FFFFFF,t_70