Binäre suche mit Java, system falls Zahl nicht vorhanden?

Moin,

Folgendes:

Ich habe ein array mit 25.000 Feldern, in diesem sind aufsteigend quadratzahlen gespeichert. Das Programm fragt aktuell ab nach welcher Zahl man sucht und sucht dann systematisch das Array ab mittels annäherung. Ich hab nur absolut keine idee wie ich es einbauen kann, dass er merkt wenn die Zahl nicht vorhanden ist. Meine idee war, das er die Variable des letzten versuchs, mit der des aktuellen versuchs dividiert und wenn das Ergebnis = 0 ist, soll er ausgeben das die zahl nicht vorhanden ist. Leider passiert es dadurch aber manchmal das er anzeigt das die Zahl nicht vorhanden ist obwohl sie das ist, immer dann wenn er ein Feld neben der gesuchten Zahl sucht. Hier mal der relevante Teil des Codes:

int resultIndex;
int bereich = 12500;
int alg = 6250;
int bereich2 = 0;

while(true)
{


    if(quadratZahlen[bereich] < zahl)
    {
        bereich = bereich + alg;
        alg = alg / 2;

    }
    else if(quadratZahlen[bereich] == zahl)
    {
        resultIndex = bereich;
        break;
    }
    else if(quadratZahlen[bereich] > zahl)
    {
        bereich = bereich / 2;

        alg = bereich / 2;

    }


    int test = bereich - bereich2;

    if (test == 0)
    {
        resultIndex = -1;
        break;
    }

    bereich2 = bereich;

}

bereich2 ist die variable der letzten suche

bereich die der aktuellen suche

alg dient nur zur neu berechnung von bereich wenn die Zahl nicht gefunden wurde

resultIndex zeigt den Platz der gefundenen Zahl

Answer 1

[KarlRanseierIII]

Wenn Du Dir es deutlich einfacher machen willst, dann nimmst Du zwei Indices, L und R und in Abhängigkeit wird dann eben R auf die Mitte zwischen L und R gesetzt oder umgekehrt.

Sobald L=R kannst Du die Schleife beenden, was einem "nicht gefunden" entspricht.

P.S.: Was ist überhaupt der Sinn in eienr Liste mit Quadratzahlen zu suchen?

Comments

[ButterkeksLp1]

Hat keinen Sinn, ist nur eine Übung an der Uni. Vielen Dank auf jeden Fall

Answer 2

[regex9]

Deine Schleife braucht im Kopf einen dynamischen Bedingungsausdruck. Da du bei einer binären Suche den Suchbereich immer weiter halbierst, hast du irgendwann (worst case) nur noch eine zu durchsuchende Menge von 1. Wenn das der Fall ist (und kein Fund vorliegt), muss die Schleife beendet werden. Die Variable resultIndex kannst du mit -1 initialisieren. Nur bei Fund wird ihr Wert überschrieben.

Nachtrag:

Eine iterative Suche könnte folgendermaßen aussehen:

int index = -1;
int start = 0;
int end = haystack.length - 1;

while (start <= end) {
  int pivot = start + (end - start) / 2;

  if (haystack[pivot] == needle) {
    index = pivot;
    break;
  }

  if (haystack[pivot] < needle) {
    start = pivot + 1;
  }
  else {
    end = pivot - 1;
  }
}

Ich verwende an dieser Stelle zwei Variablen (start, end), die die Grenzen des zu durchsuchenden Bereichs darstellen. Mit jedem Lauf werden sie neu berechnet und auf dieser Grundlage ein Mittelwert / der Ankerpunkt (Pivot) bestimmt.

Answer 3

[Verelat777]

Den Algorithmus musst Du Dir nicht selbst erschließen; Implementierungen der binären Suche findest Du im Internet, z. B. www.geeksforgeeks.org.

import java.util.List;
import java.util.ArrayList;

public class Main {
    public static void main(String args[]) {
        // Liste der Quadratzahlen generieren
        int[] quadratZahlen = new int[25000];
        for(int i = 0; i < 25000; i++) {
           quadratZahlen[i] = (int) Math.pow(i, 2);
        }

        // Wurzel finden mittels binärer Suche
        int zahl = 15129;
        int wurzel = binaereSuche(quadratZahlen, zahl);

        if(wurzel == -1) {
            System.out.println(zahl + " ist keine Quadratzahl.");
        } else {
            System.out.println("Die Wurzel von " + zahl + " ist " + wurzel + ".");
        }
    }

    // Implementierung des Algorithmus nach https://www.geeksforgeeks.org/binary-search/
    // gibt Index von x in arr[] (= entspricht der Wurzel) zurück, falls vorhanden
    public static int binaereSuche(int arr[], int x) {
        int l = 0, r = arr.length - 1;
        while(l <= r) {
            int m = l + (r - l) / 2;

            // prüfen, ob x in der Mitte liegt
            if(arr[m] == x) {
                return m;
            }

            if(arr[m] < x) {
                // wenn x größer ist, linke Hälfte ignorieren
                l = m + 1;
            } else {
                // wenn x kleiner ist, rechte Hälfte ignorieren
                r = m - 1;
            }
        }

        // x ist nicht in arr[] vorhanden, d. h. keine Quadratzahl
        return -1;
    }
}

Hierzu ein Erklärvideo zur Funktionsweise der binären Suche:

https://www.youtube.com/watch?v=XJUgCSejezQ

Woher ich das weiß: Recherche

Comments

[ButterkeksLp1]

Vielen Dank!