首页 > 代码库 > 二分查找法

二分查找法

二分查找法,顾名思义,是一种一分为二的查找算法,适用于已排序的数组(大数据量),快速地找到所查找数的位置。

源代码:

Java代码  技术分享
  1. /** 
  2.  * @param i 数组 
  3.  * @param key 要查找的Key 
  4.  * @return  
  5.  */  
  6. static int binarySearch(int[] i, int key){  
  7.     Arrays.sort(i);  
  8.     int low = 0;  
  9.     int high = i.length - 1;  
  10.     //int mid = (low + high)/2;        
  11.       
  12.     while(low <= high){              // 计算条件,数组低下标和高下标一直在计算中变化  
  13.         int mid = (low + high)>>1;   // 使用>>比除法计算效率高  
  14.         if(key > i[mid]){  
  15.             low = mid + 1;  
  16.         } else if(key < i[mid]) {  
  17.             high = mid - 1;  
  18.         } else {  
  19.             return mid;  
  20.         }  
  21.     }  
  22.       
  23.     return -1;  
  24. }  

原理:

         在数组中搜索给定Key时,先确定是有序数组,然后定义数组的最高下标和最低下标high、low,再求出数组的中间下标mid=(low+high)>>1。然后判断,当low<=high成立时,若数组[mid]值大于key时,将数组下标的底值提高为mid+1,反之将高值降低为mid-1,如此,每次将搜索的范围减小一半,大幅提高搜索效率。

附图:

技术分享

二分查找法