Binäre-Suche bei unsortierten Daten

Bitte aktiviere JavaScript!
Hallo.

Ich habe mir überlegt ob es möglich wäre, eine Binäre-Suche auch bei unsortierten Daten durchzuführen.

Ich habe hier mal folgendes programmiert. Leider funktionier hier nur die Binäre suche bei sortierten Daten. Ist es überhaupt möglich hier mit der Binären-Suche eine Zahl in den unsortierten Daten zu finden?

Danke schon mal für die Antwort.

Java:
package A1;
import java.util.Random;


 public class BinaereSuche
{
     int[] liste = new int[100]; //Array mit 100 Plätzen
     Random zufall = new Random();    // wird erzeugt für Klasse erzeugenUnsortiert()
     int n = 0;      // Anzahl der Suchschritte
     int suchzahl = 0; //Dies ist die gesuchte Zahl
     int links = 0; // linker Index
     int rechts = 99; // rechter Index         
    
     public BinaereSuche() {
        
     }
    
     // --> Sortiert
     public void erzeugeSortiert() {
            for (int i=0; i<liste.length; i++) {
            //100 Zahlen werden erzeugt
                liste[i] = i;   
            //Enthält zahlen von 1-100
            }
        }
    
     // --> Unsortiert
     public void erzeugenUnsortiert() {
            for (int i=0; i<liste.length; i++){
                int z1 = zufall.nextInt(100);
                for (int z = 0; z < i; z++) {
                    if (z1 == liste[z]) {
                        i--;
                        z=100;
                    }else{
                        liste[i] = z1;
                    }
                }
            }
        }
    
    
        public void ausgabe() {
            for (int i=0; i<liste.length; i++) {
                System.out.println(liste[i] + " || Schritt: " + (i+1));
            }
        }
        
        
        public int suchzeitBinaer(int suchzahl) {
            
            int mitte;
            do {
                mitte = (links+rechts)/2;
                n++;
                System.out.println(mitte+" Schritte: " +n);
                
                if (liste[mitte] == suchzahl) {
                    System.out.println("Suchzahl: " + mitte);
                    return mitte;
                }
                if (liste[mitte] > suchzahl) {
                    rechts = mitte-1;
                }
                if (liste[mitte] < suchzahl) {
                    links = mitte+1;
                }
                
            } while (links <= rechts && liste[mitte] != suchzahl);
            System.out.println("Zahl nicht gefunden");
            return -1;
            
            }
        
        
        }
                
        
    
    public static void main(String[] args)
    {
    
    BinaereSuche b1 = new BinaereSuche();
    //b1.erzeugeSortiert();
    b1.erzeugenUnsortiert();
    b1.suchzeitBinaer(12);
    
    }
}
 
A

Anzeige


Vielleicht hilft dir dieser Kurs hier weiter: (hier klicken)
Java:
public int lineareSuche(int suchzahl) {
  for (int i = 0; i < liste.length; i++)
    if (liste[i] == suchzahl)
      return i;
  return -1;
}
Danke.
Kann ich das auch irgendwie in die Methode suchzeitBinaer() implementieren, sodass erkannt wird, wenn es sich um strukturierte Daten und unstrukturierte Daten handelt ? Vielleicht mit einer if Abfrage ?
 
Das würde absolut nichts bringen. Um zu sehen, dass die Daten bereits sortiert sind, musst du die Liste ja einmal durchlaufen, um zu sehen, ob jede nachfolgende Zahl mindestens so groß wie die Zahl direkt davor ist. Das bedeutet, du bist dann sowieso schon einmal durch die Liste gelaufen und hättest dann auch gleich eine lineare Suche machen können. Es ist und bleibt O(n).
 
Das würde absolut nichts bringen. Um zu sehen, dass die Daten bereits sortiert sind, musst du die Liste ja einmal durchlaufen, um zu sehen, ob jede nachfolgende Zahl mindestens so groß wie die Zahl direkt davor ist. Das bedeutet, du bist dann sowieso schon einmal durch die Liste gelaufen und hättest dann auch gleich eine lineare Suche machen können. Es ist und bleibt O(n).
Ok vielen Dank. Das Ziel von mir war es, die Lineare-Suche sowie die Binäre-Suche miteinander zu vergleichen. Dabei sollte die Laufzeit der jeweiligen Verfahren bei unsortierten und sortierten Daten herausgestellt werden.
 
Das Ziel von mir war es, die Lineare-Suche sowie die Binäre-Suche miteinander zu vergleichen. Dabei sollte die Laufzeit der jeweiligen Verfahren bei unsortierten und sortierten Daten herausgestellt werden.
Dazu musst Du aber nichts implementieren, die binäre Suche erfordert nun einmal eine Sortierung. Ist diese gegeben, ist O(n) vs O(log2(n)) relativ eindeutig. Musst Du erst sortieren, wirst Du im allgemeinen Fall nicht besser als O(n*log2(n)) werden. Der Mehraufwand lohnt sich allerdings, wenn die Suche öfter benötigt wird. Willst Du n Suchen durchführen, hast Du im linearen Fall O(n²) während bei der binären Suche O(n*log2(n)) daraus werden - inkl. der Vorsortierung (die fällt damit nicht mehr ins Gewicht).
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben