二分查找，迭代和递归，java实现

直接上代码，递归式

 

package cn.edu.cqupt.serach;

public class HarfSearch {
	public static int search(int[] array,int start,int end,int target)
	{
		int middle = (start+end)/2;
		if(target==array[middle])
			return middle;
		/*
		 * 当数列只剩两个元素时{start,end}
		 * 由于middle每次都等于start，故做特殊判断
		 * 
		 */
		if(end==start+1)
			if(target==array[end])
				return end;
			else
				return -1;
		if(target<array[middle])
			return search(array,start,middle,target);
		if(target>array[middle])
			return search(array,middle,end,target);
		return -1;
	}
	public static void main(String args[])
	{
		int array[]={1,100};
		int result= search(array,0,array.length-1,1);
		System.out.println(result);
	}
}

 

 

迭代式

package cn.edu.cqupt.serach;

public class Search {
	public static  int halfSearch(int[]array,int target)
	{
		int start= 0;
		int end =array.length-1;
		while(end>start+1)
		{
			int middle=(start+end)/2;
			if(target==array[middle])
				return middle;
			if(target<array[middle])
				end=middle;
			else
				start=middle;
		}
		if(target==array[end])
			return end;
		if(target==array[start])
			return start;
		return -1;
	}
	public static void main(String args[])
	{
		int array[]={1,6,8,9,33,45,98,100};
		int result = halfSearch(array,1);
		System.out.println(result);
	}
}