第五章：数组

数组的定义

之前在定义数据的时候，大部分都是用变量来存储数据。如果我们的程序中出现大量的数据怎么办？连续输入多个数字，连续输入多个坐标点，一般而言会创建多个变量存储这些数据，显得比较麻烦。这些变量基本上类型是共通的，那我们就可以用一个容器将所有的数字进行管理。类似于字符串，字符串其实就是若干个字符的容器而已，“abc”可以通过索引/角标来获取其中某一个字符。[1,2,3,4,5]类似字符串能够也可以通过索引/角标来获取其中某一个数字呢？那么这个容器我们称之为数组。

数组主要解决多变量多数据的存储问题，方便程序后期统一维护操作数据。

数组的本质就是一系列空间大小相等且地址连续的一片存储空间。

为什么空间大小是相等的呢？就是为了方便统一维护我们的数据，必须得保证数据之间的类型是一样的。（多个同类型的变量空间连在一起组成的结构叫数组）。

为什么变量空间的地址是连续的呢？就是为了方便统一操作我们的数据。见下图

 

 

 

 1.数组就是一片地址连续且空间大小一致的存储空间(但是每个空间存的还是其他数据的地址)

2.数组存在于堆内存中，但凡在堆中存储的数据都称之为 对象

但凡在堆内存中创建的对象都会有默认初始值：整数类型默认0；浮点类型默认0.0；布尔类型默认false；引用数据类型(对象)默认null。

3.数组提供角标来访问数组当中的元素

4.数组变量存的就是数组在堆内存中首元素的地址

5.数组通过角标来访问元素的具体计算方式是 所要访问数据的地址=首元素地址+角标*数据类型大小

6.数组一旦定义下来，其长度不可改变；数组中有几个地址？就看数组有几个元素空间<==>数组的长度

7.创建数组时必须明确规定大小或内容

数据类型[] 数组名=new 数据类型[长度]：创建数组只指定长度但不指定内容

数据类型[] 数组名=new 数据类型[]{1,2,3,4,5}：创建数组指定内容(指定长度)

数据类型[] 数组名={1,2,3,4,5}：创建数组指定内容(指定长度)

[]表示是一维数组；[][]表示二维数组。

数组的内存分析:

数组常见错误:ArrayIndexOutOfBoundsException 数组角标越界;NullPointerException 空指针异常

 基本数组操作:

遍历;赋值;最大值/最小值

查找操作:

线性查找;二分查找;*斐波那契查找

public static void binarySearch(){
        //二分查找有个前提 数组必须有序
        /* 
        最好情况 查46 1次就出来了
        最坏情况 查12/60 O(logn)
        */
        int[] arr={12,17,21,32,38,41,46,49,50,50,51,59,60};
        int key=46;
        int index=-1;
        int min_index=0;
        int max_index=arr.length-1;
        int mid_index=(min_index+max_index)/2;
        while(arr[mid_index]!=key){
            if(key<arr[mid_index]){
                max_index=mid_index-1;
            }
            if(arr[mid_index]<key){
                min_index=mid_index+1;
            }
            if(min_index>max_index){
                index=-1;
                break;
            }
            mid_index=(min_index+max_index)/2;
        }
        System.out.println(mid_index);

    }

    public static void linearSearch(){
        /* 
        最好情况 查10 1次就出来了
        最坏情况 查5  10次才出来
        当数组的长度越大的话 最坏情况越差
        时间复杂度(最坏情况) O(n) 线性阶
        */
        int[] arr={10,2,8,3,1,6,4,7,9,5};
        int key=11;
        int index=-1;   //key元素不存在
        for(int i=0;i<arr.length;i++){
            if(arr[i]==key){
                index=i;
                break;
            }
        }
        System.out.println(index);
    }
}