I wrote a quick and dirty program to perform binary search with an ordered array (list) of C style strings. For example:
{"1", "12", "23", "124"}
etc (though my input set is actually much different)
NOTE:
Apologies for the confusing names -
string
is not the string,string->ID
is. (Like I said, I cobbled it together very quickly since I was writing into t a larger program). Assume all variables have been declared.I only care about program (piece) correctness and efficiency of the algorithm (for example - ignore the multiple returns etc) at the moment.
Don't worry about function calls like Log() or macros that I've used. Bottom and top are calculated off of
stringEntries
.Think of ways this will break. Don't worry about the rest of the program - just focus on this piece!
pID
is your input string. We're searching through "string"'s attribute "ID" (which is the string). Assume that "string" is actually something else, like a ptr to a struct or something, with a member "ID" which is a C-style string (null terminated and everything).len
is actuallystrlen(pID)
.
while (TRUE)
{
*string = &stringEntries[mid = (bottom + top) / 2];
if (*string == NULL) {
Log(DEBUG, _ERROR,”*string is NULL\n”);
return ERROR;
}
else if ((*string)->ID == NULL) {
Log(DEBUG, _ERROR,”(*string)->ID is NULL\n”);
return ERROR;
}
if (!(diff = strcmp(pID, (*string)->ID)))
diff = len - strlen((*string)->ID);
if (!diff) return PRESENT;
if (bottom == top) {
if (diff > 0)
(*string)++; //ignore this bit - i need it later on
return NOT_PRESENT;
}
if (diff > 0){
if (bottom == mid) bottom++;
else bottom = mid;
}
else top = mid;
}