Is it possible to have a binary search on a char * key?

[keak]

Hi there,
I am trying to seach through a sorted linked list using the binary search algorithm. My situation is I have the structure

typedef struct node
{
char *key;
int index;
struct node*nextphrase;
}

the this linked list is currently sorted against the char *key value casted into int. My question is, is this a vailid way to sort (casing a char array into int); I was wondering if "AABB" will have a same value as "BBAA" ?

 

[chipperMDW]

If you cast a [tt]char *[/tt] to an [tt]int[/tt], you get the memory address of the string. It has nothing to do with the value of the string.

 

[keak]

appologies for the confusion,
say if I am casting the value of the string into int;
in that case, should it produce a unique key for the binary search?

 

[cpjust]

An int is 4 bytes. Strings are usually much longer than 4 bytes. You would have to cast to an array of ints, otherwise words like "Progress" and "Program" will compare equal if you only look at the first 4 bytes.
Why exactly are you casting to an int anyways?

 

[Salem]

> My question is, is this a vailid way to sort (casing a char array into int)
No, use strcmp() if you want a meaningful comparison of two strings.

--

 

[ArkM]

I think the most interesting issue is: a linked list (sorted or not sorted is not a proper structure for binary search - no direct access to elements, no indicies so no a value to divide...
List implementations via (balanced) trees is the other song...

 

[lionelhill]

I can't see how you can do an efficient binary search of a linear structure unless the data units are all the same length and adjacent (i.e. a sorted array, not a linked list). Finding the half-way point in a linked list means following a lot of pointers; you might just as well search the list simply from one end to the other.
But of course reorganising the list into a binary tree makes sense if you need to search it repeatedly.

 

[keak]

Thanks for all the replies. Much appriciated.

I have been reading through, and so it looks like binary search is perhaps not the most effective algorithem for searching through my linked list ? (random string values connected with pointers)

I was wondering if someone can point out an effective method (the list usually contain about 4000~5000 linked nodes) and I am looking for a good optimization method.

I was told that hashsort has good turnaround if it contains no duplicate keys ? approachign O(1) instead of O(lg n) of a binary

 

[Salem]

> so it looks like binary search is perhaps not the most effective algorithem for searching through my linked list ?
A linked list implies a linear search.

If you want a binary search, build a tree.

But in order to be effective, you need to keep the tree roughly balanced.

Or you could just keep a regular array, and use the standard functions qsort() and bsearch() to do the work for you.

--