算法之二分法查找-PHP开发-PHP中文網

算法之二分法查找

高洛峰

發布： 2016-12-19 16:19:49

原創

1702 人瀏覽過

二分法檢索（binary search）又稱折半檢索，二分法檢索的基本思想是設字典中的元素從小到大有序地存放在數組（array）中，

首先將給定值key與字典中間位置上元素的關鍵碼(key)比較，如果相等，則檢索成功；

否則，若key小，則在字典前半部分中繼續進行二分法檢索;

若key大，則在字典後半部分中繼續進行二分法檢索。

這樣，經過一次比較就縮小一半的檢索區間，如此進行下去，直到檢索成功或檢索失敗。

偶數個取中間2個其中任何一個作為中間元素

二分法檢索是一種效率較高的檢索方法，要求字典在順序表中按關鍵碼排序。

java 碼

成功返回所在位置，失敗返回負數

package ForTest;  
  
import java.util.ArrayList;  
import java.util.Arrays;  
import java.util.List;  
  
public class Arithmetic{  
      
    public static<T extends Comparable<? super T> > int BinarySearch(List<T> 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<T extends Comparable<? super T> > int BinarySearch(T[] array, int start, int end, T key)  
    {     
        List<T> stooges = Arrays.asList(array);  
        return Arithmetic.BinarySearch(stooges, start, end, key);  
    }  
      
      
    public static void main(String[] args) {  
        // TODO Auto-generated method stub  
          
        ArrayList<Integer> a = new ArrayList<Integer>();  
          
        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中文網！