Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- faecher:informatik:oberstufe:algorithmen:binaere_suche:binsuchprogramm:start [02.07.2020 12:08] – sbel
+++ faecher:informatik:oberstufe:algorithmen:binaere_suche:binsuchprogramm:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
-====== Ein Programm zur binären Suche ======
-Arbeite mit dem folgenden Programmgerüst:
-<code java App.java>
-/**
- * Erzeugt eine geordnete Zufallsreihe und ermöglicht Abfragen darüber.
- *
- * @author Frank Schiebel
- * @version 1.0
- */
-class BinarySearch
-{
-    private int[] daten;
-    int anzahl;
-    public BinarySearch(int anzahl)
-    {
-        this.anzahl = anzahl;
-        daten = new int[anzahl];
-        int indexvorher = 0;
-        for (int i = 0; i < daten.length; i++)
-        {
-            if ( i>0 ) {
-                indexvorher = i -1;
-            }
-            daten[i] = getZufallszahlOrdered(daten[indexvorher],10*anzahl);
-        }
-    }
-    public int binaereSuche(int zahl) {
-    }
-    public void anzeigen() {
-        for (int i=0; i< anzahl; i++) {
-             System.out.println( i + " -> " + daten[i] + " ");
-        }
-    }
-    private int getZufallszahlOrdered(int basis, int grenze)
-    {
-        return (int)(2*(grenze-basis)/anzahl*Math.random()+1) + basis;
-    }
-}
-/* App Klasse. Steuerklasse für unser Programm */
-public class App {
-    public static void main(String[] args) {
-        BinarySearch liste = new BinarySearch(1000);
-        liste.anzeigen();
-    }
-}
-</code>
-===== Aufgaben: =====
-==== A1 ====
-Probiere das Programm aus. Beschreibe, was es macht, verändere auch den Parameter ''anzahl'' bei der Erzeugung des BirarySearch Objekts. Welchen Einflüsse hat diese Änderung?
-==== A2 ====
- Implementiere eine Methode ''binaereSuche'', welche den Index des gesuchten Elements zurückgibt oder ''-1'', wenn der gesuchte Wert nicht gefunden wird.
-<code java>
-    // in der main Methode der App Klasse
-    int gesucht=22;
-    int treffer = liste.binaereSuche(gesucht);
-    System.out.println("Der Wert " + gesucht + " befindet sich im Arrayelement mit dem Index " + treffer);
-</code>
-  * Die Methode ''binaereSuche'' arbeitet auf dem zuvor erzeugten Array und nimmt als Argument die gesuchte Zahl entgegen.
-  * Du führst Buch welcher Teil des Arrays zu durchsuchen ist und welcher Teil des Arrays nicht mehr in Frage kommt. wenn deine Methode startet, musst du das gesamte Array betrachten.
-{{ :faecher:informatik:oberstufe:algorithmen:binaere_suche:binsuchprogramm:step01.png |}}
-  * Jetzt musst du den Index des mittleren Elements finden, und prüfen, ob der Inhalt größer, kleiner oder gleich dem gesuchten Wert ist.
-<code java>
-  int mitte = (oben+unten)/2; //Wenn oben+unten ungerade ist, wird ''mitte'' abgerundet
-</code>
-  * Ist der Wert des Arrayelements **gleich** dem gesuchten Wert, wird der Index mit ''return'' zurückgegeben.
-  * Wenn der gesuchte Wert **kleiner** ist als der Inhalt von ''daten[mitte]'', kann die obere Hälfte des Arrays ausgeschlossen werden, indem man als neue obere Grenze ''mitte'' festlegt.
-<code java>
-if ( gesucht < daten[mitte]) {
-   oben = mitte;
-}
-</code>
-{{ :faecher:informatik:oberstufe:algorithmen:binaere_suche:binsuchprogramm:step02.png |}}
-  * Sollte der gesuchte Wert **größer** sein als ''daten[mitte]'' kann die untere Hälfte ausgeschlossen werden, dazu muss der Wert von ''unten'' auf ''mitte'' gesetzt werden.
-<code java>
-if ( gesucht > daten[mitte]) {
-   unten = mitte;
-}
-</code>