/*

折半查找
*/


class Demo
{
	public static void main(String args[])
	{
		int arr[]={2,4,7,9,15,37};
		int index=halfSearch(arr,15);
		System.out.println("index="+index);

	}

	public static int  halfSearch(int[] arr,int key)  
	{
		int min=0;
		int max=arr.length-1;
		int mid=(min+max)/2;//折半查找的特点就是在一个有序数组当中，任何一个元素都可以是前后两个元素角标的一半
		while (arr[mid]!=key)
		{
			if (key>arr[mid])
			{
				min=mid+1;
			}
			if (min>max)
			{
				return -1;
			}
			else if (key<arr[mid])
			{
				max=mid-1;
			}
			mid=(min+max)/2;
		}
	
			return mid;
	}
	
	
}