二分搜索算法

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

它的原理是：

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);  
  } 
}