Wie wird nach dem nächsten Wert in einer Nachschlagetabelle gesucht?

Question

Ich habe eine einfache eindimensionale Reihe von Integer-Werten, die eine physikalische Menge von Teilwerten darstellen, mit denen ich arbeiten muss. Ich berechne dann den Idealwert mathematisch.

Wie könnte ich einen effizienten Suchalgorithmus schreiben, der den geringsten Unterschied zu meinem Idealwert im Array findet?

Das Array ist vorbestimmt und konstant, so dass es sortiert werden kann, aber ich brauche.

Beispiel Lookup-Array:

100, 152, 256, 282, 300 

für einen idealen Wert von 125 Searching 100 im Array finden würde, während 127 152

Der tatsächliche Lookup-Array wird etwa 250 Artikel lang finden würde und nie ändern.

Answer 1

Sobald Array sortiert ist, verwenden binary search

Answer 2

Einfach durch die Array-und Computing-abs gehen (Referenz-Array-Wert [i]) würde O (N). tragen Sie den Index mit der kleinsten Differenz.

Answer 3

Python, Brute-Force auf unsortierte Liste (denn es ist Spaß beim Schreiben Python) O(n):

table = (100, 152, 256, 282, 300) 
value = 125 

lookup_dict = dict([(abs(value-x),x) for x in table]) 
closest_val = ldict[min(ldict.keys())] 

Und eine richtige Implementierung, die binäre Suche verwendet den Wert zu finden O(log_n):

import bisect 
'''Returns the closest entry in the sorted list 'sorted' to 'value' 
''' 
def find_closest(sorted, value): 
    if (value <= sorted[0]): 
     return sorted[0] 
    if (value >= sorted[-1]): 
     return sorted[-1] 
    insertpos = bisect.bisect(sorted, value) 
    if (abs(sorted[insertpos-1] - value) <= abs(sorted[insertpos] - value)): 
     return sorted[insertpos-1] 
    else: 
     return sorted[insertpos] 

Answer 4

Diese Ausnahme auf eine binäre Suche sehr ähnlich ist, wenn es um die genauen Schlüssel nicht gefunden wird, wäre es r Einen Schlüssel zu umdrehen wäre sehr nah an dem bereitgestellten Schlüssel.

Die Logik ist so lange zu suchen, bis der exakte Schlüssel gefunden wird oder bis genau ein Schlüssel zwischen High und Low übrig ist, während die Binärsuche durchgeführt wird.

Betrachten wir ein Array n [] = {1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
wenn Sie für den Schlüssel suchen: 2, dann unter Algorithmus
Schritt 1: hoch = 10, niedrig = 0, med = 5
Schritt 2: hoch = 5, niedrig = 0, med = 2
Schritt 3: hoch = 2, niedrig = 0, med = 1 In diesem Schritt wird der genaue Schlüssel gefunden. So gibt es 1.

, wenn Sie nach dem Schlüssel suchen: 3 (die in dem Array nicht vorhanden ist), dann unter Verwendung von Algorithmus
Schritt 1: hoch = 10, low = 0, med = 5
Schritt 2: hoch = 5, niedrig = 0, med = 2
Schritt 3: hoch = 2, niedrig = 0, med = 1
Schritt 4: hoch = 1, niedrig = 0, Bei diesem Schritt hoch = niedrig + 1 dh kein Element mehr zu suchen. Also gibt es med = 1 zurück.

Hoffe das hilft ...

public static <T> int binarySearch(List<T> list, T key, Comparator<T> compare) { 
       int low, high, med, c; 
       T temp; 
       high = list.size(); 
       low = 0; 
       med = (high + low)/2; 

       while (high != low+1) { 
        temp = list.get(med); 
        c = compare.compare(temp, key); 

        if (c == 0) { 
         return med; 
        } else if (c < 0){ 
         low = med; 
        }else{ 
         high = med; 
        } 

        med = (high + low)/2; 
       } 

       return med; 
      } 

    /** ------------------------ Example -------------------- **/ 

    public static void main(String[] args) { 
       List<Integer> nos = new ArrayList<Integer>(); 
       nos.addAll(Arrays.asList(new Integer[]{1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20})); 

       search(nos, 2); // Output Search:2 Key:1 Value:2 
       search(nos, 3); // Output Search:3 Key:1 Value:2 

       search(nos, 10); // Output Search:10 Key:5 Value:10 
       search(nos, 11); // Output Search:11 Key:5 Value:10 
      } 

    public static void search(List<Integer> nos, int search){ 
       int key = binarySearch(nos, search, new IntComparator()); 
       System.out.println("Search:"+search+"\tKey:"+key+"\tValue:"+nos.get(key)); 
      } 

      public static class IntComparator implements Comparator<Integer>{ 
       @Override 
       public int compare(Integer o1, Integer o2) { 
        return o1.compareTo(o2); 
       } 
      } 

Answer 5

Der binäre Suchalgorithmus von Wikipedia ist wie folgt:

int binary_search(int A[], int key, int imin, int imax) 
{ 
    // continue searching while [imin,imax] is not empty 
    while (imax >= imin) 
    { 
     // calculate the midpoint for roughly equal partition 
     int imid = midpoint(imin, imax); 
     if(A[imid] == key) 
     // key found at index imid 
     return imid; 
     // determine which subarray to search 
     else if (A[imid] < key) 
     // change min index to search upper subarray 
     imin = imid + 1; 
     else   
     // change max index to search lower subarray 
     imax = imid - 1; 
    } 
    // key was not found 
    return KEY_NOT_FOUND; 
} 

Die Endbedingung falls ein Schlüssel nicht gefunden wird, dass imax < imin ist.

Tatsächlich kann diese Bedingung die nächste Übereinstimmung finden. Die nächste Übereinstimmung wird zwischen imax und imin liegen (unter Berücksichtigung möglicherweise außerhalb der Array-Grenzen). Beachte wieder das imax < imin im Endfall. Einige Lösungen verwenden abs den Unterschied zu finden, aber wir wissen, dass A[imax] < key < A[imin] so:

if imax <= 0 return 0 
if imin >= A.count - 1 return A.count - 1 
if (key - A[imax]) < (A[imin] - key) return imax 
return imin