U
find(int* array, int element)
a) Implementieren Sie find(int* array, int element), so dass der Array- Index zur Zahl element mittels einer binären Suche ermittelt und zurückgegeben wird. Sie können Ihre Lösung anhand der vorgegebenen main-Funktion testen.
Geben Sie hierfür den Wert der Variable index nach Aufruf des Suchalgorithmus aus.
b) Passen Sie die Funktion find(int* array, int element) so an, dass -1 zurückgegeben wird, falls das gesuchte Element nicht im Array vorhanden ist.
wieso auch immer er die aufgabe so komisch unterteilt...
Hinweis: Sie brauchen im main()-Part keinerlei Änderungen vorzunehmen!!
hmm... wenn man schlechte variablen namen, ungenutzte parameter und unnötige returns mag oder es bevorzugt, wenn jede zweite zeile kommentiert ist, dann braucht man das nicht, richtig. solche zeilen g_array[i] = (sum += rand()%10); mag ich auch nicht. natürlich kann man auch const char* nutzen, obwohl char richtig wäre, aber naja...
const int my_array_size = 15;
int my_array[my_array_size];
//unsere funktion, mit einer sinnvollen signatur samt namen
int binary_find(int* arr, int arr_length, int to_search)
{
int min = 0;
int max = arr_length - 1;
for(int i = 0; min <= max; i = (min+max)/2)
{
if(to_search < arr[i])
{
max = i-1;
}
else if(arr[i] < to_search)
{
min = i+1;
}
else
{
return i;
}
}
return -1;
}
// komischer name fuer eine binaere suche, aber wir wollen ja die aufgabe auch erfüllen...
int find(int* arr, int to_search)
{
return binary_find(arr, my_array_size, to_search);
}
#include <cstdlib> //(pseudo-)zufallszahl-funktionen brauchen einen extra header
// und ich glaube nicht, dass es vom standard garantiert ist, dass iostream cstdlib einbindet
#include <iostream>
int main()
{
using namespace std;
// falls man nicht jedes mal die gleichen zahlen möchte:
//srand( reinterpret_cast<unsigned int>(&main) );
// oder:
//srand( static_cast<unsigned int>(time(0)) );
// erfordert noch ein #include <ctime>
int sum = 0;
for (int i = 0; i < my_array_size; i++)
{
int new_number = rand()%10;
sum += new_number;
my_array[i] = sum;
}
for (int i = 0; i < my_array_size; i++)
{
cout << my_array[i] << ' ';
}
cout << endl;
int to_search = my_array[rand()%my_array_size];
int index = find(my_array, to_search);
if(index == -1)
cout << "nicht gefunden (" to_search << ')' << endl;
else
cout << "gefunden: my_array[" << index << "] == " << to_search << endl;
}
oder ganz kurz:
#include <iostream>
int main()
{
std::cout << "1, 8, 12, 12, 21, 25, 33, 41, 43, 47, 52, 57, 58, 65, 66\ngefunden: my_array[11] == 57";
}
bb
