Java基础七（数组的查找和扩缩容）

数组的查找 1、线性查找法 线性查找法将要查找的关键字key与数组中的元素逐个进行比较。这个过程持续到在列表中找到与关键字匹配的元素，或者查完列表列表也没有找到关键字为止。如果匹配成功，线性查找法返回与关键字匹配的元素在数组中的下标。如果没有匹配成功，则返回-1，下面代码中的linearSearch方法给出解决方案：

class Demo{
          
   
    public static void main(String[] args){
          
   
        int[] arr={
          
   5,1,2,4,9,7,6,3,8};
        int key=5;
        int index=search(arr,key);
        System.out.println(index);
    }
    public static int linearSearch(int[] arr,int key){
          
   
        for(int i=0;i<arr.length;i++){
          
   
            if(arr[i]==key){
          
   
                return i;
            }
        }
        return -1;
    }
}

由于线性查找法的执行时间随着数组元素的个数的增长而线性增长，所以，对于大数组而言，线性查找法的效率并不高。线性查找法的时间复杂度为O(n)。

2、二分查找法 使用二分查找法的前提是数组中的元素必须已经排好序。依旧是先将关键字与数组中的元素进行比较。考虑三种情况：

如果关键字小于中间元素只需要在数组的前一半元素中继续查找关键字 如果关键字和中间元素相等，则匹配成功，查找结束 如果关键字大于中间元素，只需要在数组的后一半元素中继续查找关键字 在下面的代码中用binSearch方法实现：

class Demo{
          
   
    public static void main(String[] args){
          
          
        int[] arr2={
          
   1,2,3,4,5,6,7,8,9};
        key=10;
        index=binarySearch(arr2,key);
        System.out.println(index);
    }
     //二分搜索：前提数组是有序的
    public static int binarySearch(int[] arr,int key){
          
   
        int min=0;
        int max=arr.length-1;
        int mid=(min+max)/2;
        while(true){
          
   
            if(arr[mid]>key){
          
   
                max=mid-1;
            }else if(arr[mid]<key){
          
   
                min=mid+1;
            }else{
          
   
                return mid;
            }
            if(min>max){
          
   
                return -1;
            }
            mid=(min+max)/2;
        }
    }

二分查找法的时间复杂度为O(logn)，线性查找法的时间复杂度为O(n)，显然二分查找法效率更高，但前提数组是有序的。所以具体的数组查找视情况而定。

数组的扩缩容 我们知道数组一旦被创建，其长度就固定不可更改，实际上创建的数组长度需要改变，那怎么办呢？这时候扩容缩容就相当重要。 扩缩容的基本思想：原数组为arr，根据需要改变的长度newLen，创建一个新的数组newArr，新数组的长度就是原来数组arr的长度加需要增加而定长度。然后遍历原来的数组中的元素，将其放入新数组，并给扩展的位置赋值。 用下面代码中的resize方法实现：

import java.util.Arrays;
class Demo{
          
   
    public static void main(String[] args){
          
     
        int[] arr={
          
   1,2,3,4,5,6,7,8,9};
        arr=resize(arr,arr.length+1);
        arr[arr.length-1]=10;
        System.out.println(Arrays.toString(arr));
    }
    //数组扩容
    public static int[] resize(int[] arr,int newLen){
          
   
        int[] newArr=new int[newLen];
        for(int i=0;i<arr.length;i++){
          
   
            newArr[i]=arr[i];
        }
        return newArr;
    }
}

这个代码中实现的是扩容，缩容只需改变参数newLen的值即可。