Algorithmus für binäre Suche

Die binäre Suche wird auch als halbe Suche bezeichnet. Die Grundidee der binären Suche besteht darin, davon auszugehen, dass die Elemente im Wörterbuch in einer geordneten Reihenfolge von klein nach groß gespeichert sind >Zuerst wird der Festwertschlüssel mit dem Schlüssel des Elements in der mittleren Position des Wörterbuchs verglichen. Wenn sie gleich sind, ist der Abruf erfolgreich

Andernfalls, wenn der Schlüssel klein ist, wird die Binärdatei verwendet Die Suche wird in der ersten Hälfte des Wörterbuchs fortgesetzt.

Wenn der Schlüssel groß ist, wird die binäre Suche in der zweiten Hälfte des Wörterbuchs fortgesetzt.

Auf diese Weise wird das Abrufintervall nach einem Vergleich um die Hälfte reduziert und dies so lange, bis der Abruf erfolgreich ist oder fehlschlägt.

Nehmen Sie eines der beiden mittleren Elemente einer geraden Zahl als mittleres Element

Binärer Abruf ist eine effizientere Abrufmethode, bei der das Wörterbuch nach Schlüssel in der Sequenztabelle sortiert werden muss .

Java-Code

Gibt den Standort erfolgreich zurück, gibt bei Fehler eine negative Zahl zurück

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));  
      
    }  
 }

Weitere verwandte Artikel zur Halbierungsmethode mit mehreren Algorithmen finden Sie auf der chinesischen PHP-Website!