数组（七）--折半查找

秒速五厘米 2021-09-14 08:32 272阅读 0赞

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

**算法步骤描述：**

> ① 首先确定整个查找区间的中间位置 mid = （ left + right ）/2 。
> 
> ② 用待查关键字值与中间位置的关键字值进行比较；　 若相等，则查找成功　 若大于，则在后（右）半个区域继续进行折半查找　 若小于，则在前（左）半个区域继续进行折半查找。
> 
> ③ 对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功， 要么查找失败。折半查找的存储结构采用一维数组存放。
> 
>     public class Demo11 {
>     	public static void main(String[] args) {
>     		int[] arr={2,3,5,6,8,9,12};
>     		int key=halfSearch_2(arr,8);
>     		System.out.println(key);
>     	}
>     
>     	//折半查找
>     	public static int halfSearch(int[] arr,int key){
>     		int min,max,mid;
>     		min=0;
>     		max=arr.length-1;
>     		mid=(min+max)/2;
>     		while(arr[mid]!=key){
>     			if(key>arr[mid])
>     				min=mid+1;
>     			else if(key<arr[mid])
>     				max=mid-1;
>     			if(min>max)
>     				return -1;//表示要查找的值不存在
>     			mid=(min+max)/2;
>     		}
>     		return mid;
>     	}
>     	
>     	//折半查找方法二
>     	public static int halfSearch_2(int[] arr,int key){
>     		int min,max,mid;
>     		min=0;
>     		max=arr.length-1;
>     		while(min<=max){
>     			mid=(min+max)>>1;//右移一位，相当于除以2
>     			if(key>arr[mid])
>     				min=mid+1;
>     			else if(key<arr[mid])
>     				max=mid-1;
>     			else 
>     				return mid;	
>     		}
>     		return -1;
>     	}
>     }
> 
>   
> 结果为：4