JavaSE基础 - 数组的折半查找（两种方法）

一般来说，我们更擅长编写顺序查找(遍历)的代码。但是数组的折半查找效率更高一点。

折半查找的原理：每次查找的范围不断缩小一半,直到max < min时终止循环。

折半查找的优缺点：（优点）比较次数少，查找速度快，平均性能好；（缺点）待查表必须有序。

下面我将使用原始数组为：12,31,44,67,89,101,120 来解释查找过程。如下图：

第一次查找：因为 arr[mid] < key,所以 min = mid + 1 = 4, mid = (min + max)/2 = 5, max不变。如下图：

第二次查找时，由于arr[mid] = key,所以查找结束，终止循环。

由于事先定义的数组数据不是能更好的Demo折半过程，但是折半查找的结果就是这样。当然，也不能忘了未查找到的情况。如下图：

代码如下（两种查找方法）：

import java.util.Scanner;

class Search 
{
	public static void main(String[] args) 
	{
		Scanner input = new Scanner(System.in);
		int[] arr = {12,31,44,67,89,101,120};

		System.out.print("Please input a int num : ");
		int key = input.nextInt();

		int index = binarySearch02(arr,key);
		System.out.println("Index = " + index);
	}

	public static int binarySearch01(int[] arr,int key)	//折半查找法-1
	{
		int min = 0,max = arr.length - 1,mid;

		mid = (max + min ) / 2;	

		while(arr[mid] != key)
		{
			if(arr[mid] < key){
				min = mid + 1;			//在中间值小于key值的前提下，min值加1。
				mid = ( min + max ) / 2;
			}else if(arr[mid] > key){
				max = mid - 1;			//在中间值大于key值的前提下，max值减1。
				mid = ( max + min ) / 2;
			}

			if(max < min) return -1;	//如果max的值小于min的值，则表示没有找到key值，终止循环。
		}

		return mid;
	}

	public static int binarySearch02(int[] arr,int key) //折半查找法-2
	{
		int min = 0,max = arr.length - 1,mid;
		
		while(min <= max){
			mid=(max + min)>>1;    //位运算右移两位，相当于除2

			if( key > arr[mid]){
				min = mid + 1;
			}else if(key < arr[mid]){
				min = mid - 1;
			}else{
				return mid;		//找到返回数组的角标值。
			}
		}
		return -1;
	}
}