Binäre Suche

Hallo,

ich brauche mal Hilfe für eine Aufgabe aus der Uni:

Für die folgende Aufgabe bildet das hier verfügbare Gerüst x.cpp den Ausgangspunkt. Im Programmgerüst ist ein Array mit aufsteigend sortierten Zahlen definiert, das mit Hilfe der Funktion

find(int* array, int element)

durchsucht werden soll.

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.

Hinweis: Sie brauchen im main()-Part keinerlei Änderungen vorzunehmen!!

Hier das Gerüst:

#include <iostream>

// This enables us to use all std definitions directly.
using namespace std;

// g_n is the number of elements
const int g_n = 15;

// The array
int g_array[g_n];

/** This function implements a binary search. /
int find(int array, int element)
{
return -1;
}

/** This is the entry point of the program. /
int main(int argc, char argv[])
{
// Fill the array in increasing order...
int sum = 0;
for (int i = 0; i < g_n; i++)
g_array[i] = (sum += rand()%10);

// Print the array to the terminal
for (int i = 0; i < g_n; i++)
cout << g_array[i] << " ";
cout << "\n";

// Select some arbitrary element
int number = g_array[rand()%g_n];

// Try to find the element using binary search
int index = find(g_array, number);

cout << "Find index with ";
cout << "g_array[index] == " << number << "\n";
cout << "index = " << index << "\n";

return 0;
}

Ich weiß nicht wo ich ansetzen bzw. wie ich es lösen soll. Hilfe ist aufjedenfall Willkommen, danke!

SeppJ

http://www.c-plusplus.net/forum/200753

Ich will keine Lösung, ich will Ansätze, Hilfe etc.

Wenn ich die Lösung wollte wär ich hier ganz klar falsch...

314159265358979

std::lower_bound

cooky451

SB23456 schrieb:

Ich will keine Lösung, ich will Ansätze, Hilfe etc.

Die Idee ist, dass du eine sortierte Liste mit Werten hast. Du halbierst dann die infrage kommenden Elemente, indem du das gesuchte Element mit dem mittleren vergleichst, und je nach dem in der höheren oder in der niedrigeren Hälfte der Liste weitersuchst.

314159265358979 schrieb:

std::lower_bound

314159265358979

dontlikeit schrieb:

314159265358979 schrieb:

std::lower_bound

Es ist eigendlich genau so wie cooky451 schon erklärt hat.
Eine sehr gute beschreibung der Algorithmus findest du auch auf Wikipedia (http://de.wikipedia.org/wiki/Binäre_Suche). Dazu auch einen Pseudocode welcher den Verlauf demonstriert.

unskilled

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