Binary search with strings

Question

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:

1. 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.

2. I only care about program (piece) correctness and efficiency of the algorithm (for example - ignore the multiple returns etc) at the moment.

3. Don't worry about function calls like Log() or macros that I've used. Bottom and top are calculated off of stringEntries.

4. Think of ways this will break. Don't worry about the rest of the program - just focus on this piece!

5. 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).

6. len is actually strlen(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;           
    }

Answer 1

There is not enough information to give a real review.
If you fill in all the type information and make it a compilable function I will review your algorithm, but based on the available code the only thing I can review is the style.

• C and C++ are two completely different languages.

  • Pick one and learn it.
    The syntax may be superficially the same but how you use it will not be.
    I will make my comments assuming you are trying to write C++ not C.

• Your layout is so horrible that it is practically unreadable.

  • Pick one of the common indenting style
    If this is a problem with cut and paste then learn how to use your editor so that you can cut/paste without tabs onto a website.

Review

while (TRUE)

C++ has it's own boolean types. true/false

        {                  

Horrible formatting. The above '{' is indented way to far especially in relation to the line it is encapsulating.

  *string = &stringEntries[mid = (bottom + top) / 2];

Assignment inside the [] is allowed but makes the code hard to read.
Prefer not to do that it is much more readable to split that into two lines.
You are not being paid to write compact code you are being paid to write easy to maintain code.

   if (!(diff = strcmp(pID, (*string)->ID)))                           
           diff = len - strlen((*string)->ID);                                         

Your naming of variables here makes this code unreadable.
Make your variable names obvious.
Don't re-use variables. In the above code it looks like diff is being used for two different purposes (or is it not?). Let the compiler optimize out the extra space you should be making the code clear.

   if (bottom == top) {
          if (diff > 0) 
                 (*string)++;  //ignore this bit - i need it later on
                 return NOT_PRESENT;                   

Absolute fail.
The indention suggests that we return when (diff > 0) but the code is not going to do that, as only the first statement after the if statement belongs to the if block. Always prefer to use statement blocks after control structures. Even if they are one liners (some people still use multi-line macro's that will break your code if you don't place it in '{' '}'

   if (diff > 0){                           
          if (bottom == mid) bottom++;                           
          else  bottom = mid;                   
   }
   else        top = mid;           

More barely readable code.
A nice alignment would be good. There are also other constructs that will help:

  if (diff > 0)
  {
      bottom = ( bottom == mid) ? bottom + 1 : mid;
  }
  else
  { 
      top    = mid;
  }