Need a efficient Search Algorithm

[Ajith Sivakumar]

Hello,

I am having a File in which i am having 5000 rows of names. I have another CArray of size 5000 which consists of some names. i have to check whether the string i.e the name in the file is there in the CArray or not.

Regards,

Ajith

[riscutiavlad]

There is no better than to iterate through the array.

Have you thought of another representation? Try using a binary search tree instead of an array.

http://en.wikipedia.org/wiki/Binary_search_tree

[Yves M]

Or you could sort the CArray and then do a binary search (like std::binary_search from <algorithm>)

[suchuhui80]

I have been writting such algorithm ,
my method is storing all of the names in an binary-tree ( to save time I adopt stl::map directly , it is well-design , but lacks some efficiency ) which
acts as a dictionary , the next move is putting each word from file into that dictionary to search (each word is seperated by ' ' ) .
To make it faster use binary-search in sorted array which contains all of the names (I think you argree with my point that more dangerous more fast in C++ )
if the names and file are some sepecial character just like chinese ,
I would adopt an-other way ,make an array whose each element is a pointer to the binary-tree or array above ,which includes a total of 65535 element . Under the layout , each element represents a chinese character (one chinese character has the length of 2 byte , while english character has then length of 1 bytes , that is why I make a array with the length of 65535 ) . Therefor ,the data-structure is constituted by linear array (It acts like a hash ) and binary-tree (or sorted array )
Therefor , the search has one more step than the upper one ,
the added step is to take the first chinese character from file and put it in the linear-array to search , the token chinese-character whose length is 2 byte is acted as an index, and the search will be definately fast , through the search we will get the corresponding element which is binary-tree or sorted array , afterwards take the remining chinese-character to search in the element .

[StTwister]

I think a hash table would be best suited in this situation