二分搜索算法

/*
*  二分搜索算法用于针对已排序的集合进行搜索。

它的原理是：

1，  找到排序数组的中间元素，如果它匹配目标值，那么就返回它在数组中的索引。

2，  如果没有找到，那么判断中间值比目标值大还是小，

如果中间值比目标值大，那么就对第一个元素到middle-1的元素递归这个过程。

如果中间值比目标值小，那么就对middle+1到最后一个元素。

3，  如果结束的索引小于开始的索引，返回-1，表示没有找到。

4，  如果子集合有2个元素，那么各自比较。因为Java的整数除法会舍弃小数，如果数组只有2个元素，那么middle值一直都是第一个元素。

经过上述的递归过程，最终将返回匹配元素的索引，或者是-1，表示找不到。
*/

public class BinarySearh {
	public static void main(String[] args){
		 int[] array = {13,27,38,49,65,76,97};
		 int n = sq_Dichotomy_Search(array,0,array.length-1,38);
		 System.out.println(n);
	}
	
	
	public static int binarySearh(int[] array,int start,int end,int value){
		int middle = (start+end)/2;
		if(start>end){
			return -1;
		}
		if(start==(end-1)){
			if(array[start]==value){
				return start;
			}else if(array[end]==value){
				return end;
			}else{
				return -1;
			}
		}else if(array[middle]==value){
			return middle;
		}else if(array[middle]>value){
			return binarySearh(array,start,middle,value);
		}else if(array[middle]<value){
			return binarySearh(array,middle,end,value);
		}
			return -1;
	}

/*
*   有序数组二分查找算法函数sq_Dichotomy_Search0<用数组实现> 
     参数描述： 
         int array[]    :被查找数组 
         int n        :被查找数组元素个数 
         int key        :被查找的关键值 
     返回值: 
         如果没有找到:    sq_Dichotomy_Search0 = -1 
         否则:            sq_Dichotomy_Search0 = key数组下标 
*/

public static int binarySearh2(int array[],int start,int end,int key){   
	     int low,high,mid;   
	     low = start;   
	     high = end;   
	        
	     while(low<=high){   
	         mid = (high+low)/2;   
	         if(array[mid] == key)   
	             return(mid);   
	         /**//*key>array[mid] 表明要求查找的值在[mid+1,high]*/  
	         /**//*否则,在[low,mid-1]*/  
	         if(key > array[mid])   
	             low = mid + 1;   
	         else  
	             high = mid - 1;   
	     }   
	     return(-1);   
	 }

/**//* 
     有序数组插值查找算法函数sq_Dichotomy_Search1<用数组实现> 
     (插值查找算法是二分查找算法的改进) 
     参数描述： 
         int array[]    :被查找数组 
         int n        :被查找数组元素个数 
         int key        :被查找的关键值 
     返回值: 
         如果没有找到:    sq_Dichotomy_Search1 = -1 
         否则:            sq_Dichotomy_Search1 = key数组下标 
*/ 
 

public static int sq_Dichotomy_Search(int array[],int start,int end,int key)   {   
	      int low,high,        //二分数组的上,下标   
	          pos;            //查找码的大致(估算)位置   
	      low = 0;   
	      high = end;   
	      while(low <= high){   
	          pos = (key-array[low])/(array[high]-array[low])*(high-low)+low;   
	          /**//*找到关键值,中途退出*/  
	          if(key == array[pos])   
	              return(pos);   
	          if(key > array[pos])   
	              low = pos + 1;   
	          else  
	              high = pos - 1;   
	      }   
	      /**//*没有找到,返回-1*/  
	      return(-1);   
	  }  
}