アルゴリズム二分探索-PHP开发-php.cn

アルゴリズム二分探索

高洛峰

リリース： 2016-12-19 16:19:49

オリジナル

1704 人が閲覧しました

二分探索は半探索とも呼ばれます。二分探索の基本的な考え方は、辞書内の要素が小さいものから大きいものへと順番に配列(配列)に格納されていると仮定することです。キーと辞書の中央の値が同じ位置にある要素のキーを比較します。等しければ、検索は成功します。そうでない場合は、辞書の前半で二分探索を続けます。 ;

キーが大きい場合は、辞書の後半を検索します。で二分探索を続けます。

このようにして、1 回の比較の後、検索間隔は半分に短縮され、これは検索が成功するか失敗するまで続きます。

偶数の中から真ん中の 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 中国語 Web サイトに注目してください。