5.5 数组常用操作（2）

这一节我们接上一节继续学习数组的常用操作。 数组的查找 这个功能我们以后会经常用到，这里我们先看一个对普通数组的查找方法 ~~~ /* 数组常见功能:查找. */ public static int getIndex(int[] arr,int x) { for(int i=0;i<arr.length;i++)//从第一个元素开始找 { if(arr[i] == x)//如果找到对应元素则返回当前元素索引 { return i; } } return -1;//如果没有找到该元素则返回索引值-1 } ~~~ 上面的方法是一个普通的查找方法，因为我们在查找过程中可能对所有的元素都找一遍。 下面我们就看一个非常有名的查找算法，那就折半查找，也叫做二分查找。当然这个方法有一前提，那就是该数组必须为有序数组。 ~~~ public static int binarySearch(int[] arr,int key) { int min,mid,max;//定义三个变量做为三个指针 min = 0;//min代表最左边的指针 mid = (min + max) / 2;//mid代表中间的指针 max = arr.length-1;//max代表最右边的指针 while(arr[mid] != key)//当mid所指向的元素不等于key时，继续查找，否则则终止循环 { if(key > arr[mid])//如果mid指向的元素小于key,则让最左边的min指针指向mid+1的位置 min = mid + 1; else if(key < arr[mid])//反之则让最右边的max指针指向mid-1位置 max = mid - 1; if(max < min)//如果出现max指针小于min指针时，说明没有找到key对应的元素，则返回-1 return -1; mid = (min + max) / 2;//对中间的指针重新指向左右两个指针的中点 } return mid;//当跳出循环说明找到了 } ~~~ 再看另一个相同的的方法 ~~~ public static int binarySearch_2(int[] arr,int key) { int min,mid,max; int min = 0; int max = arr.length-1; while(min <= max)//当min>max则终止循环,返回-1 { mid = (min + max) >> 1;//在循环内找出min指针和max指针的中点元素，>>1等同于除以2 if(key > arr[mid])//如果mid指向的元素小于key,则让最左边的min指针指向mid+1的位置 min = mid + 1; else if(key < arr[mid])//反之则让最右边的max指针指向mid-1位置 max = mid - 1; else return mid;//否则就是key = arr[mid],那当然就是找到了 } return -1; } ~~~ 我们测试一下 ~~~ import java.util.*; class ArrayDemo6 { public static void main(String[] args) { int[] arr = new int[]{43,56,98,2,5,36};//无序数组 int x = getIndex(arr,3); System.out.println("x="+x); int[] arr2 = new int[]{3,9,12,19,23,45};//有序数组 int index = binarySearch(arr2,15); System.out.println("index="+index); int index1 = binarySearch_2(arr2,19); System.out.println("index1="+index1); //真实开发中，我们运用Arrays类中的binarySearch(Object[] a,Object key)方法 int index2 = Arrays.binarySearch(arr2,45);//如果存在,返回具体的角标位置 System.out.println("index2="+index2); int index3 = Arrays.binarySearch(arr2,21);//如果不存在,返回的就是这个数的插入点(return -插入点-1) System.out.println("index3="+index3); } } ~~~ 结果：  我们看到Arrays类中的binarySearch(Object[] a,Object key)方法实现了数组的二分查找，并且当查找不元素不存在时，返回值的其实指明了该key可以插入数组并且数组仍然有序的插入点。我们在实际开发中直接用这个方法就可以了。