数组

数组Array 是一个线性表数据结构，它用一组连续的内存空间来存储相同类型的元素。
上述就是数组最重要的定义，理解这句话基本就理解了数组。
下面详述其特点

线性表

线性表中的数据最多有两个方向 前和后。
常见的线性表有 数组 链表 队列 栈等等

非线性表

树 图 这种并非只有简单的前后关系

连续的内存空间存储相同的数据

这个一特点实现了数组的下标访问

int a[10]

数组内存地址.jpg

寻址公式为 a[i] = 初始地址 + i * 数据类型大小
a[6] = 1000 + 6 * 4
a[6] = 1024

数组的相关操作

插入

k：插入的位置
有序 ：如果k位置有元素 则要将包括k位置元素后的所有元素依次搬移一个位置 时间复杂度为O(n)
无序：将k位置元素放到数组元素的最后 将k位置元素赋值为插入元素 时间复杂度为O(1)

删除

k：删除的位置
有序：与插入相同，如果k位置元素被删除k之后的所有数据都需要搬移 时间复杂度为O(n)
在删除时可以对删除元素标记为已删除，当已删除元素达到阈值统一删除，可避免频繁的搬移元素
无序：删除k元素后将数组中最后的元素填充到k位置 时间复杂度O(n)

查找

有序：使用二分查找 O(logn)
无序：顺序遍历O(n)

LeetCode704二分查找

class Solution {
    public int search(int[] nums, int target) {
        int start = 0, end = nums.length - 1, middle = 0;
        while(!(start > end)) {
            middle = start + (end - start >> 1);
            if(nums[middle] > target) {
                end = middle - 1;
            } else if(nums[middle] < target) {
                start = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }
}