Suche im Array

20.01.2015, 19:38

neuling96

Suche im Array

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:

public class Suche {
public static boolean suchebinaer(int a, int [] array){
if(array.length==1 && a != array[0]) {
return false;
}else {
int m= array.length/2;
if(array[m]==a){
return true;
}else {
if(array[m]>a){
int[]arrayx=new int [m];
for(int i=0; i<m; i++){
arrayx[i]=array[i];
}
return suchebinaer(a, arrayx);
}else {
int[]arrayx=new int [m];
for(int i=0; i<m; i++){
arrayx[i]=array[i+m];
}
return suchebinaer(a, arrayx);
}
}
}
}
}

keine compilerfehler und ich glaube das passt so???

20.01.2015, 19:44

Auf diesen Beitrag antworten »

eulerscheZahl

code:
1:	suchebinaer(3, new int[] { 1, 2, 3, 7, 9, 13 })

liefert mir false, obwohl da eine 3 drin ist.

Die Idee, das Array für den Methodenaufruf zu kopieren, gefällt mir nicht (denke an den Speicher, der da unnötig belegt wird, das macht das Programm unnötig langsam. Übergebe lieber das ganze Array sowie Start und Ende des Suchintervalls.

20.01.2015, 19:59

Auf diesen Beitrag antworten »

neuling96

ich sehe den einen fall habe ich nicht betratet

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:


public class Suche {
public static boolean suchebinaer(int a, int [] array){
if(array.length==1 && a != array[0]) {
return false;
}else {
int m= array.length/2;
if(array[m]==a){
return true;
}else {
if(array[m]>=a){
int[]arrayx=new int [m+1];
for(int i=0; i<=m; i++){
arrayx[i]=array[i];
}
return suchebinaer(a, arrayx);
}else {
int[]arrayx=new int [m];
for(int i=0; i<m; i++){
arrayx[i]=array[i+m];
}
return suchebinaer(a, arrayx);
}
}
}
}
}

"Übergebe lieber das ganze Array sowie Start und Ende des Suchintervalls"
ich weiß nicht wie ich es umsetzten soll

20.01.2015, 20:04

Auf diesen Beitrag antworten »

eulerscheZahl

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

private static boolean suchebinaer(int a, int[] array, int start, int end) {
	int mitte = (start + end) / 2;
	return array[mitte] == a || suchebinaer(a, array, start, mitte - 1)
			|| suchebinaer(a, array, mitte + 1, end);

}

public static boolean suchebinaer(int a, int[] array) {
	if (array.length == 0) {
		return false;
	}
	return suchebinaer(a, array, 0, array.length - 1);
}

20.01.2015, 20:13

Auf diesen Beitrag antworten »

neuling96

wow das ist kurz! und so schnell gelöst großes Grinsen

würde ich für mein code punkt abzüge bekommen, wegen der Ineffizienz ?

20.01.2015, 20:14

Auf diesen Beitrag antworten »

eulerscheZahl

Keine Ahnung, ich weiß nicht, was von dir erwartet wird.

20.01.2015, 20:20

Auf diesen Beitrag antworten »

neuling96

ich auch nicht großes Grinsen

die uni sieht nicht vor weiter in java zu vertiefen!
Es wird noch Hoare-Kalkül und Datenstrukturen eingeführt und das wars dann mit java.
kannst du Themen empfehlen, die ich unbedingt behandelt haben soll?

20.01.2015, 20:23

Auf diesen Beitrag antworten »

eulerscheZahl

Zum einen ist das von Uni zu Uni verschieden, zum anderen bin ich glaube ich nicht qualifiziert, das zu beantworten, ich studiere nicht einmal Informatik. Wirf einfach einen Blick ins Modulhandbuch, da steht doch drin, was alles behandelt wird.

20.01.2015, 20:27

Auf diesen Beitrag antworten »

neuling96

oha kein Infostudent und so gut geschockt

wie immer vielen dank Wink

20.01.2015, 20:30

Auf diesen Beitrag antworten »

eulerscheZahl

Nur beim Programmieren. Ich studiere Elektro-und Informationstechnik. Da lerne ich zwar auch Programmieren, boolsche Algebra und so. Aber im theoretischen Bereich sieht es nicht so gut aus, das Hoare-Kalkül sagt mir nur vom Namen her etwas.

20.01.2015, 20:43

Auf diesen Beitrag antworten »

neuling96

nochmal wow großes Grinsen

hast du dir programmieren selbst beigebracht?

20.01.2015, 20:47

Auf diesen Beitrag antworten »

eulerscheZahl

Im Studium hatte ich bereits 2 Semester C und eins C++, zur Zeit noch Java.
In der Schule man ein wenig Delphi (die Sprache ist zwar objektorientiert, aber wir kamen noch nichtmal bis zu Funktionen, haben alles in die main geschrieben.
Ich habe mich dann selbst weiter damit beschäftigt und mir auch C# beigebracht. Mit den beiden Sprachen programmiere ich auch in der Arbeit (Delphi nur, um alten Code zu reparieren).

21.01.2015, 15:57

Auf diesen Beitrag antworten »

neuling96

Zitat:

Original von eulerscheZahl

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

private static boolean suchebinaer(int a, int[] array, int start, int end) {
	int mitte = (start + end) / 2;
	return array[mitte] == a || suchebinaer(a, array, start, mitte - 1)
			|| suchebinaer(a, array, mitte + 1, end);

}

public static boolean suchebinaer(int a, int[] array) {
	if (array.length == 0) {
		return false;
	}
	return suchebinaer(a, array, 0, array.length - 1);
}

für (5, new int[] { 1, 2,3, 7, 13 }))
liefert ?

21.01.2015, 16:04

Auf diesen Beitrag antworten »

eulerscheZahl

Da habe ich die Abbruchbedinung verbockt.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:

private static boolean suchebinaer(int a, int[] array, int start, int end) {
	if (start >= end) {
		return array[start] == a;
	}
	int mitte = (start + end) / 2;
	return array[mitte] == a 
			|| suchebinaer(a, array, start, mitte - 1)
			|| suchebinaer(a, array, mitte + 1, end);
}

sollte jetzt passen.

21.01.2015, 16:18

Auf diesen Beitrag antworten »

neuling96

ja danke

21.01.2015, 16:39

Auf diesen Beitrag antworten »

neuling96

Zitat:

Original von neuling96

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:


public class Suche {
public static boolean suchebinaer(int a, int [] array){
if(array.length==1 && a != array[0]) {
return false;
}else {
int m= array.length/2;
if(array[m]==a){
return true;
}else {
if(array[m]>=a){
int[]arrayx=new int [m+1];
for(int i=0; i<=m; i++){
arrayx[i]=array[i];
}
return suchebinaer(a, arrayx);
}else {
int[]arrayx=new int [m];
for(int i=0; i<m; i++){
arrayx[i]=array[i+m];
}
return suchebinaer(a, arrayx);
}
}
}
}
}

würdet man diesen code als rekursiv bezeichnen?
ich mein es "ruft" sich doch selbst wieder auf? verwirrt

, also ja ?

21.01.2015, 16:41

Auf diesen Beitrag antworten »

eulerscheZahl

Ja.

21.01.2015, 17:38

Auf diesen Beitrag antworten »

neuling96

. Falls nein, wird die Suche auf der
vorderen Halfte (falls der Suchwert kleiner ist) oder hinteren Halfte des Arrays wiederholt.

wenn ich dein code geanu ansehe, dann läuft es nicht nach diesen schema, oder ??
, aber ich bin mir nicht sicher

ich hab versucht dein code um zuschreiben
public class Suche {
private static boolean suchebinaer(int a, int[] array, int start, int end) {
if (start >= end) {
return array[start] == a;
}else{
int mitte = (start + end) / 2;
if (array[mitte] == a) {
return true;
}else{
if (array[mitte] > a){
return suchebinaer(a, array, start, mitte - 1);
}else{
return suchebinaer(a, array, mitte + 1, end);
}
}
}
}
public static boolean suchebinaer(int a, int[] array) {
if (array.length == 0) {
return false;
}else{
return suchebinaer(a, array, 0, array.length - 1);
}
}
}

21.01.2015, 17:43

Auf diesen Beitrag antworten »

eulerscheZahl

Nein, das was ich geschrieben habe, ist keine binäre Suche. Ich wollte dir nur zeigen, wie du das Kopieren des Array vermeiden kannst.
Sieht gut aus, wie du die Unterscheidung des zu durchsuchenden Intervalls eingebaut hast.

Neue Frage »

Antworten »

Suche im Array

Verwandte Themen