数组的常见功能——查找

我们定义并初始化一个数组后，有时需要查找数组中某一个元素的位置，这时我们便要用到数组的查找功能，我们常用的查找某个元素的方法，有两种：一种是针对无序数组的普通查找，另一种是针对有序数组的折半查找功能。

一、普通查找

普通查找方法的思想是，将需要查找的元素与数组中的元素一个个进行比对，直到查到目标元素或者数组的最后一个角标。因此，此方法适用于无序数组。

class Search 
{
	public static void main(String[] args) 
	{
		int[] arr = {1,97,5,87,34,98};
		int Index = search(arr,34);//查找元素34对应数组中的角标
		System.out.println("Index="+Index);
	}
	
	//普通查找
	public static int search(int[] arr,int key)
	{
		for ( int i=0 ; i<arr.length ; i++ )
		{
			if( arr[i]==key)
				return i;
		}
		return -1;
	}
}

运行结果

数组的常见功能——查找

二、折半查找

如下图，折半查找方的思想是，针对一个有序数组，定义3个变量：min=数组的首角标、max=数组的尾角标、mid=(min+max)/2，将目标元素与mid角标对应的数组元素进行比较，若目标元素小于mid角标对应的数组元素，那么max=mid-1；若目标元素大于mid角标对应的数组元素，那么min=mid+1，直到找到目标元素等于mid角标对应的数组元素或者max<min查找停止。因此，此方法适用于有序数组。

数组的常见功能——查找

代码实现：

//折半查找的前提是数组有序
class  SearchDemo
{
	public static void main(String[] args) 
	{
		int[] arr = {1,13,25,26,29,104,567,789,990};
		int Index = halfSearch(arr,29);  //查找29对应的角标
		int Index2 = halfSearch_2(arr,104); //查找104对应的角标
		System.out.println("Index="+Index);
		System.out.println("Index2="+Index2);
	}


	//折半查找（二分查找）
	public static int halfSearch(int[] arr, int key)
	{
		int max,min,mid;
		min = 0;
		max = arr.length-1;
		mid = (max+min)/2;
		while(arr[mid]!=key)
		{
			if(key>arr[mid])
				min = mid+1;
			else if(key<arr[mid])
				max = mid-1;
			if(max<min)
				return -1;
			mid = (max+min)/2;
		}
			return mid;
	}

	//折半查找方法二
	public static int halfSearch_2(int[] arr, int key)
	{
		int max,min,mid;
		min = 0;
		max = arr.length-1;
		while(min<=max)
		{
			mid = (max+min)>>1;//相当于mid = (max+min)/2
			if(key>arr[mid])
				min = mid+1;
			else if(key<arr[mid])
				max = mid-1;
			else
				return mid;
		}
		return -1;
	}
}

运行结果

数组的常见功能——查找

面试题

给定一个有序的数组，如果给这个数组存储一个元素，并保证这个数组还是有序的，那么这个元素的存储的角标该如何获取

{1,13,25,26,29,104,567,789,990}

代码实现（参考折半查找的图三理解）：

class  SearchDemo_2
{
	public static void main(String[] args) 
	{
		int[] arr = {1,13,25,26,29,104,567,789,990};
		int Index = halfSearch_2(arr,50);
		System.out.println("Index="+Index);
	}

	//折半查找
	public static int halfSearch_2(int[] arr, int key)
	{
		int max,min,mid;
		min = 0;
		max = arr.length-1;
		while(min<=max)
		{
			mid = (max+min)>>1;//相当于min = (max+min)/2
			if(key>arr[mid])
				min = mid+1;
			else if(key<arr[mid])
				max = mid-1;
			else
				return mid;
		}
		return min;//此处是重点
	} 
}

运行结果

数组的常见功能——查找

本题代码中的重点，便是当 max < min 时的返回值，可以参照折半查找中的图三进行理解。

总结

实际上，Java有自带的查找功能，即调用函数 Array.binarySearch(数组，查找元素)，如果查找元素存在数组中，则返回的具体角标位置，不存在则返回 —插入点—1。虽然Java为我们提供了便利，但是我们还是需要明白折半查找的原理，因为我们明白了原理以后，就算使用其他编程语言，也可以灵活运用。

数组的常见功能——查找

一、普通查找

二、折半查找

面试题

总结

相关推荐