当前位置: 代码迷 >> Java相关 >> 温习折半查找的两种实现方法
  详细解决方案

温习折半查找的两种实现方法

热度:89   发布时间:2016-04-22 20:40:31.0
复习折半查找的两种实现方法

折半查找:必须是在有序的表中进行。这是重要的一点。这折半查找提高了效率。

 1.待查找数据值比中间元素值小,则以整个查找范围的前半部分作为新的查找范围。

2.待查找数据值比中间元素值大,则以整个查找范围的后半部分作为新的查找范围。

一种是实现的角标;一种是直接实现的数值。

//折半查找就是找到,必须是有序的列表。
public class halfsearch {
 public static void mian(String args[]){
  
  
  int[]arry={1,10,51,3,4,5};
  int jg=halfSearch(arry, 2);
  System.out.print(jg);
  
  
 }
 //折半查找第一种方法
  public static int halfSearch(int[] arry,int key){
         int min=0;
         //最大的角表;
         int max=arry.length-1;
         int mid;
        
         while(max>min){
          mid=(min+max)/2;
          if(key>mid){
           min=mid+1;
          }
          else if(key<mid) {
           max=mid=1;
          }else
           //返回的是角标
           return mid;
         }
         //不再范围内的时候就是越界反悔-1
  return -1;
  
  
  }
//第二种方法
  public static int halfSearch_2(int[] arry,int key){
   int min=0;
   int max=arry.length-1;
   int mid=(min+max)/2;
   //比较的是中间的值和要找的值进行比较
   while(key!=arry[mid]){
    if(key>arry[mid]){
     min=mid+1;
    }else if(key<arry[mid]){
     max=mid-1; 
    }
    //如果最大的值和最小的值重合以后返回-1
    else if(min>max){
     return -1;
     }
     mid=(min+max)/2;
   
   }
  
    return mid;
  
  
  }
}

  相关解决方案