这一节我们接上一节继续学习数组的常用操作。
数组的查找
这个功能我们以后会经常用到，这里我们先看一个对普通数组的查找方法
/*
数组常见功能:查找.
*/
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可以插入数组并且数组仍然有序的插入点。我们在实际开发中直接用这个方法就可以了。