Unendliche Schleife in der binären Suchvariante (Java)

Question

Mein Ziel ist es, einen Schlüssel und ein Array einzugeben und dann die Anzahl der Werte in diesem Array, die kleiner oder gleich dem Schlüssel sind, mithilfe der binären Suche auszugeben.

Dies ist mein Code:

import java.util.*; 
import java.io.*; 

public class search { 
    public static void main(String[] args) { 
     Scanner scan = new Scanner(System.in); 
     int key = scan.nextInt(); 
     int size = scan.nextInt(); 
     int [] array = new int [size]; 

     for (int i = 0;i < size ;i++) { 
      array[i] = scan.nextInt(); 
     } 
     Arrays.sort(array); 

     System.out.println(binary(key, array)); 
    } 

    public static int binary (int key, int [] array){ 
     int lo = 0; 
     int hi = array.length - 1; 

     while (lo < hi){ 
      int mid = (lo + hi)/2; 
      if (array[mid] <= key){ 
       lo = mid; 
      } 

      else { 
       hi = mid - 1; 
      } 
     } 

     return lo + 1; 
    } 
} 

Mit dem Datenschlüssel = 5, array = {2,4,6,7}, das Programm funktioniert. Aber sobald drei Werte sind, die kleiner oder gleich dem Schlüssel sind, geht es drunter und drüber. Zum Beispiel erzeugt key = 5, array = {2,4,5,6} eine Endlosschleife. Ich habe den Grund dafür gefunden, aber ich verstehe nicht, wie ich das umgehen soll.

Grundsätzlich wird der mid Wert immer als derselbe Wert berechnet. Was kann ich tun, um dies zu umgehen? Wenn der Code von Natur aus falsch ist, bedeutet das, dass the set solution for a USACO problem falsch war.

Answer 1

Die Probenlösung scheint in Ordnung. Das Problem mit Ihrem Code ist, dass mid = (lo + hi)/2 rundet auf lo, die ein Problem ist, da die Update-Fälle lo = mid und hi = mid - 1 sind. Bei hi == lo + 1 wird im ersten Fall kein Fortschritt gemacht. Sie sollten zusammenrunden, wie das Beispiel tut: mid = (lo + hi + 1)/2 (Warnung: kann bei langen Arrays überlaufen; überprüfen Sie Ihre Einschränkungen).

Das Beispiel überprüft auch, ob der erste Wert kleiner als der Schlüssel ist.

Answer 2

Ihr Algorithmus scheint in Ordnung zu sein. Aber ich sehe ein Problem mit der Zuweisung des Wertes für Mitte.

int mid = (hi+lo)/2 

denken Sie an einen Fall, in dem Ihr

hi=4 
mid = 3 

nun der neue Wert für Mitte sein wird (3 + 4)/2 = 3 (Integer-Division)

so wird die Schleife fortgesetzt Laufen ohne zu brechen.

In diesem Fall können Sie den Wert von mid erhöhen, indem Sie diese Bedingung überprüfen.

Aber effektiver scheint es besser überprüfen Sie den Wert von Mitte wiederholt, dann brechen Sie die Schleife. Endlich prüft, ob der Wert von array [hallo] das gleiche wie Ihr Array ist [mid]

Hope this helfen würde ..

einen schönen Tag .. :)

EDIT

würde ein besserer Weg zu tun seine

ändern while-Schleife zu

while(mid<hi+1){ 
} 

dann prüfen, für die Gleichheit der Werte nach der Schleife ..

ODER Einfach gesetzt

mid = (mid+hi+1)/2 

Answer 3

In Ihrer Schleife müssen Sie Ihre Intervalle immer kleiner machen und Sie müssen auch das Element ausschließen, das Sie gerade betrachtet haben. Sie tun das, wenn Sie nach links gehen, aber nicht, wenn Sie nach rechts gehen.

Sie verpassen auch Intervalle der Länge 1, weil Sie inklusive der unteren und oberen Grenzen verwenden. Ihre Schleifenbedingung sollte lo <= hi sein.

Schließlich geben Sie eins zu viele zurück: Die Ergebnisse sollten 0 sein, wenn der Schlüssel kleiner als das erste Element ist, und es sollte die Array-Länge sein, wenn es größer als das letzte Element ist. So

:

static int binary(int key, int[] array) 
{ 
    int lo = 0; 
    int hi = array.length - 1; 

    while (lo <= hi) { 
     int mid = (lo + hi)/2; 

     if (array[mid] <= key) { 
      lo = mid + 1; 
     } else { 
      hi = mid - 1; 
     } 
    } 

    return lo; 
} 

Meiner Meinung nach ist es besser, eine exklusive Obergrenze zu verwenden, wie Java in der Regel der Fall ist. (Beispielsweise hat ein Array der Länge n Elemente bei Indizes 0 bis n - 1, die obere Grenze n liegt außerhalb des gültigen Bereichs.) Wenn nichts anderes, ist es mit anderem Java-Code konsistent. Also:

static int binary(int key, int[] array) 
{ 
    int lo = 0; 
    int hi = array.length; 

    while (lo < hi) { 
     int mid = (lo + hi)/2; 

     if (array[mid] <= key) { 
      lo = mid + 1; 
     } else { 
      hi = mid; 
     } 
    } 

    return lo; 
}