Binary search on cstrings

Question

This implements binary search on an array of cstrings. One thing I'm wondering about is it faster or slower to pass a variable as const i.e. len. Also strcmp() gets called a lot and since I can't find any specific details on how it works, is it worthwhile to make my own function? For example does it immediately return a value if the first character of each arguments are different?

/*
*IN: scope: array of cstrings to be searched
*IN: len: length of array
*IN: find: cstring to be found
*OUT: true if find is in scope, otherwise false
*/
bool binSrch(char** scope, const int len, char* find)
{
   int c, first, last, middle;

   first = 0;
   last = len - 1;
   middle = (first+last)/2;

   while( first <= last )
   {
      if (strcmp(scope[middle], find) < 0 )
         first = middle + 1;
      else if (strcmp(scope[middle], find) == 0)
      {
         return true;
      }
      else
         last = middle - 1;

      middle = (first + last)/2;
   }
   if ( first > last )
      return false;
}

EDIT: is there a way to intelligently choose the pivot point? For example if your looking in a phone book for a name starting with Z you wouldn't start at the middle you'd start closer to the back.

This question appears to be off-topic because it is about trying to understand the code snippet and not about seeking a review. — Jamal
– Jamal, Commented Oct 5, 2013 at 8:31
@Jamal this is my second post on this site so I'm still learning :) what makes you say I don't understand the code, the fact I point out some areas I see pitfalls? Would you rather I have posted just the code and not said anything? — Celeritas
– Celeritas, Commented Oct 5, 2013 at 8:52
It's working code, posted with some notes about concerns. I see nothing wrong with the question. — 200_success
– 200_success, Commented Oct 5, 2013 at 9:15

200_success · Accepted Answer · 2013-10-05 08:50:34Z

2

You can assume that the implementation of strcmp() is not stupid. A lot of code out there relies on strcmp(), so rest assured that a lot of work has gone into optimizing it. Nevertheless, you don't want to call it twice per iteration through your loop.

Interestingly, len is the only parameter that doesn't need to be declared const, since it is passed by value. In contrast, scope and find are passed by reference, so a promise that binSrch() won't alter them would be helpful.

At the end, you don't need to test for first > last before returning false. The only way you can get past the while loop is with first > last.

You have an unused variable c. Avoid such mistakes by getting into the habit of assigning right away:

int first = 0,
    last = len - 1,
    middle = (first + last) / 2;

I think the braces on your else if look weird. Either remove them, or put them everywhere consistently. (I prefer the latter.)

answered Oct 5, 2013 at 8:50

200_success

146k22 gold badges191 silver badges481 bronze badges

\$\begingroup\$ "promise that binSrch() won't alter them would be helpful" I could use a refresher on this, so if a pointer is passed as const that means the value it points to doesn't change right? Or does it mean the address the pointer points to doesn't change? \$\endgroup\$

Celeritas
– Celeritas

2013-10-05 08:56:57 +00:00
Commented Oct 5, 2013 at 8:56
\$\begingroup\$ It depends on where you put the const. In your case, feel free to sprinkle const liberally, since you never mutate anything. bool binSrch(char const *const *scope, int len, char const* find) would work. \$\endgroup\$

200_success
– 200_success

2013-10-05 09:12:04 +00:00
Commented Oct 5, 2013 at 9:12
\$\begingroup\$ Right so since I'm not changing the value or address pointed two should I use two const on each variable e.g. char const * const find? Perhaps that's a question by itself... \$\endgroup\$

Celeritas
– Celeritas

2013-10-05 09:30:30 +00:00
Commented Oct 5, 2013 at 9:30
\$\begingroup\$ char const * const find would be a bit like const int len — correct, but superfluous and unimportant from the caller's point of view. \$\endgroup\$

200_success
– 200_success

2013-10-05 09:40:07 +00:00
Commented Oct 5, 2013 at 9:40

Add a comment |

William Morris · Accepted Answer · 2013-10-10 17:33:21Z

A few comments:

I don't much like double pointers so I would probably define a type to be passed:
```
typedef const char* String;
```
Then let's define the function
```
int binSrch(const String *list, size_t len, const char *find)
```
You can still pass an array of char* to this. I have added some const, used size_t for the array length (which is common with standard library functions) and replaced the bool with an int - which I prefer.
Your code duplicates this line:
```
middle = (first+last)/2;
```
and uses different spacing for each. Just do it once.
Your brackets are inconsistent. I prefer to see brackets even when not strictly needed.
Your duplicate strcmp calls should be removed.

Here is how it ends up:

int binSrch(const String *list, size_t len, const char *find)
{
  int start = 0;
  int end = len;
  while (start < end) {
      int middle = (start + end) / 2;
      int comp = strcmp(list[middle], find);
      if (comp < 0 ) {
          start = middle + 1;
      }
      else if (comp > 0) {
          end = middle;
      }
      else return 1;
  }
  return 0;
}

Stack Exchange Network

Binary search on cstrings

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Binary search on cstrings

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions