Array mit einer Variablen überprüfen

[Tiyen]

Hallo zusammen,

habe ein dickes Problem, und zwar habe ich eine Aufgabenstellung bekommen, die lautet man solle eine Zahl eingeben, und das Programm berechnet dann an welcher Stelle die Zahl sich im Array befindet. Quasi eine Binäre Suche.
Bis jetzt habe ich es schon geschafft auszugeben, an welcher Stelle sich die Zahl befindet. Ich muss jetzt nur noch das Array durchlaufen um zu überprüfen, ob die eingegeben Zahl sich auch wirklich im Array befindet. Wenn nicht soll eben eine Fehlermeldung ausgegeben werden. Könnte ihr mir da vielleicht weiterhelfen ?

import java.util.Scanner;

public class BinäreSuche {
	public static void main(String args[]) {

		int array[] = { 1, 5, 8, 9, 11, 22, 23, 59, 77, 88 };
		int eingabe = 0;
		int obergrenze = array.length;
		int untergrenze = 0;
		int mitte = (obergrenze - untergrenze) / 2;
		int i = 0;


		Scanner input = new Scanner(System.in);

		System.out.print("Zu suchende Zahl eingeben: ");
		eingabe = input.nextInt();
		input.close();
	
		while (eingabe != array[mitte]) {
			if (eingabe < array[mitte]) {
				obergrenze = mitte - 1;
				mitte = (obergrenze - untergrenze) / 2;

				if (eingabe == array[mitte]) {
					System.out.println(eingabe + " ist an der Stelle "
							+ (mitte + 1));
				}
			}

			else if (eingabe > array[mitte]) {
				untergrenze = mitte + 1;
				mitte = (untergrenze + obergrenze) / 2;

				if (eingabe == array[mitte]) {
					System.out.println(eingabe + " ist an der Stelle "
							+ (mitte + 1));
				}
			}
		}
	}

}

 

[HonniCilest]

Die binäre Suche (in deinem Fall iterativ) sieht aber ein wenig anders aus...
http://en.wikipedia.org/wiki/Binary_search_algorithm
Du machst es dir komplizierter, als es ist.

Hast du ansonsten irgendwelche Vorgaben? Sonst könntest du dir auch Vorhandenes zu Nutze machen:
http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#binarySearch(int[], int)

 

[4by4]

geg: ein Array mit beliebigen Zahlen.
zB: {1, 5, 7, 9, 18, 39, 49, 56, 59, 62, 63, 71, 85, 98}
ACHTUNG Array muss sortiert sein!

Die zu suchende Zahl: key = 5

Obere Grenze: array.length - 1 (= 13);
Untere Grenze: 0

Anschließend wird die Zahl in der Mitte gesucht:
int m = (o + u) / 2
m = (13 + 0) / 2 = 6 (java schneidet bei Integer die Kommazahlen einfach Weg)
{1, 5, 7, 9, 18, 39, 49, 56, 59, 62, 63, 71, 85, 98}
  u		               m                                        o

a[m] == key?
Ausgabe von m

a[m] > key
Ab Stern "*" nur mit o = m;

a[m] < key
Ab Stern "*" nur mit u = m + 1;

Tipp:
Pack dies in eine Methode und ruf diese recursiv auf


******************************************************************
Wenn du was lernen willst stoppe hier

******************************************************************














































import java.util.Scanner;

public class BinarySearch {

	private static Scanner sc;

	public static void main(String[] args) {
		
		//initalisiere array
		int[] array = {1, 5, 7, 9, 18, 39, 49, 56, 59, 62, 63, 71, 85, 98};
		System.out.println("******************* Binary Search *******************");
		
		//Array wird ausgegeben
		System.out.println(java.util.Arrays.toString(array));
		System.out.println("Geben Sie bitte die Zahl ein die Sie suchen möchten: ");
		
		//Zu suchende Zahl wird eingelesen
		int key = sc.nextInt();
		System.out.println("Die Zahl befindet sich auf Position" 
				+ "\n(-1 Zahl konnte nicht gefunden werden): " 
				
				//Übergibt der Methode das Array, die zu suchende Zahl, untere Grenze, obere Grenze
				+ binarySearch(array, key, 0, array.length - 1));
	}

	private static int binarySearch(int[] array, int key, int u, int o) {
		
		//ermittelt den Mittelpunkt
		int m = (u + o) / 2;
		
		//Wenn Mittelpunkt == zu suchende Zahl, gib diese zurück
		if(array[m] == key)
			return m;
		
		//Wenn Mittelpunkt größer, rufe Methode erneut auf mit neuer Obergrenze m
		else if(array[m] > key && o - u > 0)
			return binarySearch(array, key, u, m);
		
		//Wenn Mittelpunkt größer, rufe Methode erneut auf mit neuer Untergrenze m + 1
		else if(array[m] < key && o - u > 0)
			return binarySearch(array, key, m + 1, o);
		else
		//ansonsten gib -1 zurück
			return -1;
	}
}

 

[HonniCilest]

@4by4 normalerweise geben wir keine kompletten Lösungen bei Schulaufgaben vor (und die Beschreibung klingt definitiv nach einer Schulaufgabe), TO soll ja auch was lernen.