kann ich binary_search für wörter suche nutzen?

T0bi

hi mal ne frage, wenn ich mit binary_search nach zahlen werte suche gibt die fkt mir ja nur ne boolsche antwort zurueck, kann ich also auch mit binary_search eine datei auslasen und so nach einen wort suchen? also erst die datei in einen vector laden und dann suchen?, geht das ueberhaupt ne komplette datei in einen vector zuladen?

GPC

Hallo,

binäre suche funktioniert nur auf geordneten Datenstrukturen (und kann durchaus den Index zurückliefern). Du kannst damit suchen, was du willst, nur es muss halt geordnet vorliegen. Ich schätze mal, deine Datei liegt nicht geordnet vor... .

Wenn du oft suchen musst, lohnt es sich womöglich, die Daten zu sortieren bzw. sortiert zu halten. Andernfalls reicht vllt. eine Sequentielle Suche schon aus.

MfG

GPC

T0bi

sequentielle suche... ich weiss net was du meinst koenntest dus mir mal erklaeren, THX

Braunstein

sequentielle Suche - ein Element nach dem anderern überprüfen

SideWinder

Für den Anfang könntes du Wort für Wort in ein std::set einlesen und dieses zum Suchen benützen.

Wenn das klappt kannst du versuchen dich über Google zu einer Hashmap vorzuarbeiten

MfG SideWinder

Werner Salomon

T0bi schrieb:

hi mal ne frage, wenn ich mit binary_search nach zahlen werte suche gibt die fkt mir ja nur ne boolsche antwort zurueck, kann ich also auch mit binary_search eine datei auslasen und so nach einen wort suchen? also erst die datei in einen vector laden und dann suchen?, geht das ueberhaupt ne komplette datei in einen vector zuladen?

'binary_search' sagt Dir nur, ob das was Du suchst in dem vorgegebenen Intervall vorhanden ist oder nicht. Wie schon erwähnt setzt es eine geordnete Reihenfolge voraus.

Datei mit Wörtern in vector laden ist auch kein Problem.

std::ifstream file( "Datei.txt" );
  std::vector< std::string > v( std::istream_iterator< std::string >( file ), 
    std::istream_iterator< std::string >() ); // .. is drin

  // dann sortieren
  std::sort( v.begin(), v.end() );
  if( std::binary_search( v.begin(), v.end(), "Hallo" ) )
    std::cout << "Wort 'Hallo' ist enthalten " << std::endl;

Wenn Du nur einmal - also nur ein Wort - suchst, ist 'find' sicher schneller. Funktionieren sollte auch folgendes (ohne Container):

std::ifstream file( "Datei.txt" );
  if( std::find( std::istream_iterator< std::string >( file ), 
          std::istream_iterator< std::string >(), "Hallo" ) 
      != std::istream_iterator< std::string >() ) 
    std::cout << "Wort 'Hallo' ist enthalten " << std::endl;

Wenn Du öfter suchst, loht sich evt. auch der set. Das geht so:

std::ifstream file( "Datei.txt" );
  std::set< std::string > s;
  std::copy( std::istream_iterator< std::string >( file ), 
          std::istream_iterator< std::string >(), 
          std::inserter( s, s.begin() ) );
  if( s.find( "Hallo" ) != s.end() )
    std::cout << "Wort 'Hallo' ist enthalten " << std::endl;

der set.find ist immer eine binäre Suche.

Gruß
Werner

T0bi

thanx werner.
nur noch mal um sicher zugehen ist es dan also richtig wenn ich wörter so in ein set packe?:

#include<vcl.h>
#include<string>
#include<set>
#include<iostream>
    using namespace std;

int main()
{

    string neuesWort;
    set< string > Woerterbuch;
    set< string >::iterator iter;

    cout << " Gib ein Wort ein! : "; cin >> neuesWort;

    cout << "\n Gib noch ein Wort ein! : "; cin >> neuesWort;

    Woerterbuch.insert( neuesWort );

    cout << "\n\n Derzeitig sich befindene Woerter im Woerterbuch:\n\n ";

    for ( iter = Woerterbuch.begin(); iter != Woerterbuch.end(); ++iter ) {

        int i = 1;

        cout << i << ".Wort -  " << *iter << "\n ";
        ++i;
    }

    cin.sync();
    cin.get();
    return 0;
}
//---------------------------------------------------------------------------

doch eine frage, denn ich weiss ich hab was falsch gemacht *g*, wenn der iterator durchs woerterbuch blaettert und mir alles wörter raus suchen soll gibt er mir nur das letzte wieder aus, wieso???

GPC

Werner Salomon schrieb:

T0bi schrieb:

hi mal ne frage, wenn ich mit binary_search nach zahlen werte suche gibt die fkt mir ja nur ne boolsche antwort zurueck, kann ich also auch mit binary_search eine datei auslasen und so nach einen wort suchen? also erst die datei in einen vector laden und dann suchen?, geht das ueberhaupt ne komplette datei in einen vector zuladen?

'binary_search' sagt Dir nur, ob das was Du suchst in dem vorgegebenen Intervall vorhanden ist oder nicht.

Kann man ja auch leicht selber schreiben, um den Index zurückzukriegen:

template <typename T>
  int bsearch(T *array, size_t l, size_t u, const T& t) {
    if (l>u)
      return -1;

    size_t m = (l+u)/2;
    if (array[m] < t)
      return bsearchr(array,m+1,u,t);
    else if (array[m] == t)
      return m;
    else if (array[m] > t)
      return bsearchr(array,l,m-1,t);
  };

nur noch mal um sicher zugehen ist es dan also richtig wenn ich wörter so in ein set packe?:

passt.

doch eine frage, denn ich weiss ich hab was falsch gemacht *g*, wenn der iterator durchs woerterbuch blaettert und mir alles wörter raus suchen soll gibt er mir nur das letzte wieder aus, wieso???

Du solltest vllt. gleich nach dem ersten Einlesen ins set einfügen, weil so wie du's jetzt machst, überschreibst du ja neuesWort beim zweiten Einlesen. So ist's korrekt:

cout << " Gib ein Wort ein! : "; cin >> neuesWort;

    Woerterbuch.insert( neuesWort );  //blub... das hier fehlte

    cout << "\n Gib noch ein Wort ein! : "; cin >> neuesWort;

    Woerterbuch.insert( neuesWort );

EDIT: Quote tags in Ordnung gebracht

MfG

GPC

T0bi

alles klar funktioniert supi... nur eins vllt. noch, wie kann ich die var i erhöhgen das dann 1. wort, 2. wort erscheint und nicht immer 1. wort, 1. wort ????

Braunstein

indem du das int i = 0; aus der for-Schleife raus nimmst. So deklarierst du i bei jedem Schleifendurchlauf neu.