Re: Informatik Nachhilfe
kannst du hier deine version reinposten, weil ich bin etwas zu faul den ganzen blatt abzuschreiben
aber da gabs sicherlich dieses eine problem mit index aus zwei zahlen.
Re: Informatik Nachhilfe
/*
* binairSearch.java
*
* Created on 26. April 2008, 22:41
*
* To change this template, choose Tools | Template Manager
* and open the template in the editor.
*/
/**
* BinairSearch
* Die 1 Methode sollte Index einer bestimmter Zahl aus einer Sortierte Array zuruckgeben.
* Die 2 Methode sollte eine Array mit allen Indexen einer bestimmter Zahl aus einer Sortierte Array zuruckgeben.(mit linearSearch Erweiterert)
*
* @author Vladimir Parashin
* @version 1.1
* ,da es vielleicht noch kürzer und schneller sein kann.
*/
public class binairSearch {
/**Binaire Suche - Methode den Array auf ein bestimmte Integer zu durchsuchen und deren Indexen zurückzugeben
* @param toSearch Integer das man finden soll
* @param toCheck Array wo man das Integer Finden soll
* @return der Index des gesuchten Integers*/
public static int binairSearch(int toSearch,int [] toCheck){
int Erg = 0;
int Mindex;
int [] originalA = Arraycope(toCheck,toCheck.length,0);
boolean stop = false;
while(stop != true){ //Die Haupt-Schleiffe
if(toCheck.length % 2 == 1){ //Teilbarkeit Test
Mindex =((toCheck.length+1)/2)-1;
}else if(toCheck.length % 2 == 0) {
Mindex =((toCheck.length)/2)-1;
}else{
throw new RuntimeException("Falscher Eingabe,die Array aus "+toCheck.length
+" Elementen kann nicht Durchsucht werden;");
}
if(toCheck.length == 1 && toCheck[Mindex] != toSearch){ //Die Ausgabe falls es das Ergebniss nicht gibt
System.out.println("Die Array hat den gesuchten Element nicht");
stop = true;
Erg = -1;
}else if(toCheck[Mindex] > toSearch){ //Die 1.Überprüffung !>!
int [] dummy = Arraycope(toCheck,Mindex,0);
toCheck = Arraycope(dummy,dummy.length,0);
}else if(toCheck[Mindex] < toSearch){ //Die 2.Überprüffung !<!
int [] dummy = Arraycope(toCheck,toCheck.length-(Mindex+1),Mindex+1);
toCheck = Arraycope(dummy,dummy.length,0);
Erg=Erg+1+Mindex;
}else { //Die 3.Überprüffung !=!,was Automatisch ein Ergebniss zurückgibt
Erg= Erg+Mindex;
stop = true;
System.out.println("Die Array hat den gesuchten Element an der >"+Erg+"< Stelle.");
return Erg;
}
}
return Erg;
}
/**Binaire Suche 2 - Methode den Array auf ein bestimmte Integer zu durchsuchen und deren Index zurückzugeben
* Mit Erweiterung das es alle Indexen zuruckgibt wo es im Array den Zahl gibt. In Form eine Array
* @param toSearch Integer das man finden soll
* @param toCheck Array wo man das Integer Finden soll
* @return der Array aus Ergebnissen*/
public static int [] binairSearchExpansion(int toSearch,int [] toCheck){
int c = 0;
int ec = 0;
int Erg = 0;
int Mindex;
int[] AllErg = new int[1];
int [] originalA = Arraycope(toCheck,toCheck.length,0);
boolean stop = false;
while(stop != true){
if(toCheck.length % 2 == 1){
Mindex =((toCheck.length+1)/2)-1;
}else if(toCheck.length % 2 == 0) {
Mindex =((toCheck.length)/2)-1;
}else{
throw new RuntimeException("Falscher Eingabe,die Array aus "+toCheck.length
+" Elementen kann nicht Durchsucht werden;");
}
if(toCheck.length == 1 && toCheck[Mindex] != toSearch){ //Die Ausgabe falls es Ergebniss nicht gibt
System.out.println("Die Array hat den gesuchten Element nicht");
stop = true;
AllErg = null;
}else if(toCheck[Mindex] > toSearch){
int [] dummy = Arraycope(toCheck,Mindex,0);
toCheck = Arraycope(dummy,dummy.length,0);
}else if(toCheck[Mindex] < toSearch){
int [] dummy = Arraycope(toCheck,toCheck.length-(Mindex+1),Mindex+1);
toCheck = Arraycope(dummy,dummy.length,0);
Erg=Erg+1+Mindex;
}else { //Die 3.Überprüffung !=!,was Automatisch ein Ergebniss zurückgibt
Erg= Erg+Mindex;
stop = true;
for(int i=Erg+1;i<originalA.length && originalA[i]==toSearch;i++){c++;}
for(int x= Erg-1 ;x>-1 && originalA[x]==toSearch;x--){ec++;}
AllErg = new int[ec+c+1]; //Array aus Ergebnissen
for(int end = 0;end<AllErg.length;end++){
AllErg[end] = Erg-ec;
Erg++;
}
System.out.println("Der Element wurde an folgenden Indexen Gefunde :");
for(int s = 0;s<AllErg.length;s++){
System.out.println(AllErg[s]);
}
}
}
return AllErg;
}
/** Wandelt einen Array in eine andere (spezifische)Array um
* @param toCope ein beliebiger Array aus Integern
* @param NAlength die länge der (spezifische)Array
* @param Sindex Anfangsstelle wo das Kopieren anfängt
* @return das(spezifische)Arrays */
public static int [] Arraycope(int[] toCope,int NAlength,int Sindex) {
int[] dummy = new int[NAlength];
System.arraycopy(toCope,Sindex,dummy,0,NAlength);
return dummy;
}
/** BubbleSort-Variante ohne Obergrenze
* @param toSort der noch nicht sortierte Array aus Integern
* @return der sortierte Array */
public static int [] bubbleSort(int[] toSort) { // das Methode zu Sortieren
boolean stop = false;
while(stop == false){ // Warte bis Stop Schleife
stop = true;
for(int i = 0;i<toSort.length-1;i++){ //Alle Objekte in Array durchgehen
if(toSort[i] >toSort[i+1]){
int temp = toSort[i]; // Tauschen
toSort[i] = toSort[i+1];
toSort[i+1]= temp;
stop = false;
}
}
}
return toSort;
}
public static void main(String args[]){ // Test
int [] a = new int [2];
a[0]= 0;
a[1]= 1;
a = bubbleSort(a); //Sortiert Zuerst das Array
for(int x = 0;x<a.length;x++){
System.out.println(a[x]);
}
int index = binairSearch(452,a); //Testiert 1. Methode
int [] indexes = binairSearchExpansion(452,a); //Testiert 2. Methode
}
}
Was dich nicht umbringt,
Macht dich nur noch Stärker.
Proffessor.Dr.Drewer
Re: Informatik Nachhilfe
ja da ist der folgende fehler gibn z.b tSearch 32 ein, und arry aus 47 und 68
dann siehst du was passiert....
nämlich ArrayIndexOutOfBoundsExeption;
-1
ja jetzt ist die frage wie soll man das beheben?
Re: Informatik Nachhilfe
HIER DAS PROGRAMM ORIGINAL AUS JAVA VERZEICHNISS (das meintest du Vladimir oder?)
public class BinarySearch
{
public static final int NOT_FOUND = -1;
/**
* Performs the standard binary search
* using two comparisons per level.
* @return index where item is found, or NOT_FOUND.
*/
public static int binarySearch( Comparable [ ] a, Comparable x )
{
int low = 0;
int high = a.length - 1;
int mid;
while( low <= high )
{
mid = ( low + high ) / 2;
if( a[ mid ].compareTo( x ) < 0 )
low = mid + 1;
else if( a[ mid ].compareTo( x ) > 0 )
high = mid - 1;
else
return mid;
}
return NOT_FOUND; // NOT_FOUND = -1
}
// Test program
public static void main( String [ ] args )
{
int SIZE = 8;
Comparable [ ] a = new Integer [ SIZE ];
for( int i = 0; i < SIZE; i++ )
a[ i ] = new Integer( i * 2 );
for( int i = 0; i < SIZE * 2; i++ )
System.out.println( "Found " + i + " at " +
binarySearch( a, new Integer( i ) ) );
}
}
Re: Informatik Nachhilfe
nicht gantz,
/**
* Searches the specified array of ints for the specified value using the
* binary search algorithm. The array must be sorted (as
* by the {@link #sort(int[])} method) prior to making this call. If it
* is not sorted, the results are undefined. If the array contains
* multiple elements with the specified value, there is no guarantee which
* one will be found.
*
* @param a the array to be searched
* @param key the value to be searched for
* @return index of the search key, if it is contained in the array;
* otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
* <i>insertion point</i> is defined as the point at which the
* key would be inserted into the array: the index of the first
* element greater than the key, or <tt>a.length</tt> if all
* elements in the array are less than the specified key. Note
* that this guarantees that the return value will be >= 0 if
* and only if the key is found.
*/
public static int binarySearch(int[] a, int key) {
return binarySearch0(a, 0, a.length, key);
}
// Like public version, but without range checks.
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
Tja das Programm ist proffesionall gemacht 
,nehmen wir mal ne Beispiel an solche Leute.
Was dich nicht umbringt,
Macht dich nur noch Stärker.
Proffessor.Dr.Drewer