算法之二分法查找

二分法检索（binary search）又称折半检索，二分法检索的基本思想是设字典中的元素从小到大有序地存放在数组（array）中，

首先将给定值key与字典中间位置上元素的关键码(key)比较，如果相等，则检索成功；

否则，若key小，则在字典前半部分中继续进行二分法检索;

若key大，则在字典后半部分中继续进行二分法检索。

这样，经过一次比较就缩小一半的检索区间，如此进行下去，直到检索成功或检索失败。

偶数个取中间2个其中任何一个作为中间元素

WaStar 网上花店系统

系统特点： 商品多级分类检索、搜索，支持同一商品多重分类，自由设置显示式样 自由设置会员类型，自由设置权限项目，自由分配每种会员类型和每个会员的权限 灵活的商品定价，最多12级价格自由分配给各种会员类型或会员，也可针对单会员单商品特殊定价 强大的会员管理、帐户管理、订单管理功能和一系列帐务查询统计功能 灵活的会员积分系统，自由设置每个积分事件的积分计算方法 灵活的网站内容发布、管理系统，每个栏目可

下载

二分法检索是一种效率较高的检索方法，要求字典在顺序表中按关键码排序。

java 代码 

成功返回所在位置，失败返回负数

package ForTest;  
  
import java.util.ArrayList;  
import java.util.Arrays;  
import java.util.List;  
  
public class Arithmetic{  
      
    public static > int BinarySearch(List array, int start, int end, T key)  
    {         
        int low;  
        int high;         
        int guess;  
          
        if(array == null || start>end || start > array.size()-1 || end < 0)  
        {  
            return -1;  
        }    
          
        start = start < 0 ? 0 : start;  
        low  = start-1;  
          
        end = end > array.size()-1 ? array.size()-1 : end;   
        high = end+1;   
          
          
        while (high - low > 1) {  
            guess = ((high - low)>>1)  + low;  
  
            if (array.get(guess).compareTo(key) < 0)  
                low = guess;  
            else  
                high = guess;  
        }  
  
        if (high == end +1 )  
        {  
             return ~(end +1 );  
        }             
        else if (array.get(high).compareTo(key) == 0)  
        {  
             return high;  
        }  
        else  
        {  
            return ~high;         
        }        
    }  
    public static > int BinarySearch(T[] array, int start, int end, T key)  
    {     
        List stooges = Arrays.asList(array);  
        return Arithmetic.BinarySearch(stooges, start, end, key);  
    }  
      
      
    public static void main(String[] args) {  
        // TODO Auto-generated method stub  
          
        ArrayList a = new ArrayList();  
          
        Float[] b = new Float[100];  
       
          
        for(int i=0; i<100; i++)  
        {  
            a.add(i);    
            b[i] = (float) i;  
              
        }         
          System.out.println(""+Arithmetic.BinarySearch(a,0,1000,200));  
          System.out.println(""+Arithmetic.BinarySearch(b,0,100,2.f));  
      
    }  
 }

更多算法之二分法查找相关文章请关注PHP中文网！