Suche nach einem Fall, wenn die binäre Suche fehlschlägt

Question

Ich versuche, eine wirklich interessante Programmieraufgabe zu lösen, und ich bin irgendwie außerhalb der Ideen, warum mein Code fehlschlägt. Hier ist sie:

Write eine Funktion, die, da eine Liste und eine Zielsumme, kehrt Null basierenden Indizes von irgendwelchen zwei verschiedenen Elementen, deren Summe gleich die Zielsumme. Wenn solche Elemente nicht vorhanden sind, sollte die Funktion null zurückgeben. Zum Beispiel findTwoSum (new int [] {1, 3, 5, 7, 9}, 12), wenn eine der folgenden Tupel von Indizes zurück:

1, 4 (3 + 9 = 12) 
2, 3 (5 + 7 = 12) 
3, 2 (7 + 5 = 12) 
4, 1 (9 + 3 = 12) 

sollten einfach sein oder? Also hier ist meine Funktion:

public static int[] findTwoSum(int[] list, int sum) { 
     int[] indices = null; 
     for(int i = 0; i < list.length; i++) { 
      int currentNum = list[i]; 
      int findNum = sum - currentNum; 
      int length = list.length; 
      int min = i; 
      int max = length-1; 

      while(max >= min) { 
       int guess = (max+min)/2; 

       if(list[guess] == findNum) { 
        return new int[] {i,guess}; 
       } 

       if(list[guess] < findNum) { 
        min = guess + 1; 
       } 

       if(list[guess] > findNum) { 
        max = guess - 1; 
       } 
      } 

     } 


     return indices; 
    } 

-Code ist ziemlich einfach, für jedes Element im Array, versucht es mit binärer Suche, ein weiteres Elemente zu finden, so dass ihre Summe der bereitgestellten sum gleich ist. Ich habe diesen Code getestet und konnte kein Szenario finden, in dem es fehlschlägt, vorausgesetzt, das angegebene Array ist sortiert. Allerdings, wenn ich diesen Code auf TestDome ausführen, schlägt der letzte Fall fehl, es ist irgendwie falsche Lösung. Kann jemand darauf hinweisen, was mit diesem Ansatz nicht stimmt?

Answer 1

Der Code geht davon aus, dass die Liste sortiert ist. Die Problemaussage sagt nichts über die Reihenfolge der Elemente aus, daher müssen Sie das Array selbst sortieren. Da Sie Indizes benötigen, müssen Sie Wertepaare und Indizes sortieren.

Ein schnellerer Ansatz besteht darin, die Daten in eine Hash-Tabelle mit Zählwerten und ursprünglichen Indizes zu stellen und in der Liste auf Target - n für jede n zu prüfen. Sie müssen für den Spezialfall zählen, wenn gleich 2*n ist.

Answer 2

Basierend auf der Frage und Klarstellung des Autors in Bezug auf die sortierte Reihenfolge der ursprünglichen Liste scheint es, dass die ursprüngliche Liste nicht sortiert ist. Daher muss die Liste sortiert werden und die ursprünglichen Indizes müssen separat in einer anderen Liste gespeichert werden.

Nach dem Sortieren des Arrays und Beachten der ursprünglichen Indizes, lassen Sie uns sagen, dass arr[] enthält die sortierte Liste und indices[] enthält die ursprünglichen Indizes der entsprechenden Elemente in arr[]. In einfacheren Worten gibt indices[i] den ursprünglichen Index des Elements arr[i].

Jetzt können Sie den 2-SUM-Algorithmus für die Suche nach dem Paar folgen:

• initialisieren zwei Indexvariablen dem Kandidaten Elemente im sortierten Feld zu finden.

  • Initialize zuerst auf den am weitesten links stehenden Index: l = 0
  • Initialize zweiten der äußerste rechte Index: r = ar_size-1

• Schleife während L < r.

  • If (arr [l] + arr [r] == sum) dann Paar (Indizes [l], Indizes [r]) return
  • Else if (arr [l] + arr [r] < Summe), dann l ++
  • Else r--
• keine Kandidaten in ganzer Reihe - NULL

Sie kehren können auch Ihre binäre Suchtechnik anstelle der 2-SUM Verfahren verwenden.

Hoffe es hilft !!

Answer 3

Versuchen Sie diese Lösung. Es sortiert das Array und verwendet eine binäre Suche, um das zweite Element zu finden, das sum - n sein muss.

Wenn ein passendes Paar gefunden wird, wird es in der ursprünglichen Anordnung nachgeschlagen den ursprünglichen Index zu bestimmen:

public static int[] findTwoSum(int[] list, int sum) { 
    int len = list.length; 
    int[] sortedList= Arrays.copyOf(list, len); 
    Arrays.sort(sortedList); 
    for (int i = 0; i < len; i++) { 
     int m = list[i]; 
     int j = Arrays.binarySearch(sortedList, sum - m); 
     if (j >= 0 && i != j) 
      return new int[] { i, findIndex(list, sortedList[j]) }; 
    } 
    return null; 
} 

public static int findIndex(int[] list, int m) { 
    int len = list.length; 
    for (int i = 0; i < len; i++) { 
     if (list[i] == m) 
      return i; 
    } 
    return -1; 
}