Comments are welcome for two sequential search C functions

[lovecreatesbeauty]

Any comments are welcome for following the two sequential search C
functions of both integer and string versions. Though they are simple,
please do not laugh at it Could you give your great suggestion to
it? Thanks a lot.

/*sequentially search a array of integers for a value. val: the integer
is to be searched for in the array, array: array of integers, len: item
count in the array. return the index of the value found in array, -1
for failure. the algotithm efficience of the function is O(n). - jhl,
Jul 2006*/

#include <stddef.h>

int lookup(int val, const int array[], int len)
{
int i = -1;

if (array != NULL && len != 0){
for (i = 0; i < len; ++i){
if (val == array){
break;
}
}
}
return i;
}

/*sequentially search a string array for a word. word: the word is to
be searched for in the array, array: array of word string, len: item
count in the array. return the index of the value found in array, -1
for failure. the algotithm efficience of the function is O(n). - jhl,
Jul 2006*/

#include <string.h>

int slookup(const char *word, const char *array[], int len)
{
int i = -1;

if (word != NULL && array != NULL && len != 0){
for (i = 0; i < len; ++i){
if (strcmp(word, array) == 0){
break;
}
}
}
return i;
}

 

[Richard Heathfield]

lovecreatesbeauty said:

Any comments are welcome for following the two sequential search C
functions of both integer and string versions. Though they are simple,
please do not laugh at it Could you give your great suggestion to
it? Thanks a lot.

/*sequentially search a array of integers for a value. val: the integer
is to be searched for in the array, array: array of integers, len: item
count in the array. return the index of the value found in array, -1
for failure. the algotithm efficience of the function is O(n). - jhl,
Jul 2006*/

#include <stddef.h>

int lookup(int val, const int array[], int len)
{
int i = -1;

if (array != NULL && len != 0){
for (i = 0; i < len; ++i){
if (val == array){
break;
}
}
}
return i;
}

(a) either you should warn your users that a return value of len means "not
found", or you should add a check before the return:

if(i == len)
{
i = -1;
}

(b) here is a way to write it without break:

int lookup(val, const int array[], int len)
{
int i = -1;
if(array != NULL && len != 0)
{
while(i < len && val != array)
{
++i;
}
if(i == len)
{
i = -1;
}
}
return i;
}

/*sequentially search a string array for a word. word: the word is to
be searched for in the array, array: array of word string, len: item
count in the array. return the index of the value found in array, -1
for failure. the algotithm efficience of the function is O(n). - jhl,
Jul 2006*/

#include <string.h>

int slookup(const char *word, const char *array[], int len)
{
int i = -1;

if (word != NULL && array != NULL && len != 0){
for (i = 0; i < len; ++i){
if (strcmp(word, array) == 0){
break;
}
}
}
return i;
}

Ditto, on all counts.

 

[lovecreatesbeauty]

lovecreatesbeauty said:

Any comments are welcome for following the two sequential search C
functions of both integer and string versions. Though they are simple,
please do not laugh at it Could you give your great suggestion to
it? Thanks a lot.

/*sequentially search a array of integers for a value. val: the integer
is to be searched for in the array, array: array of integers, len: item
count in the array. return the index of the value found in array, -1
for failure. the algotithm efficience of the function is O(n). - jhl,
Jul 2006*/

#include <stddef.h>

int lookup(int val, const int array[], int len)
{
int i = -1;

if (array != NULL && len != 0){
for (i = 0; i < len; ++i){
if (val == array){
break;
}
}
}
return i;
}

(a) either you should warn your users that a return value of len means "not
found", or you should add a check before the return:

Oh, len is out of range of the array. But I take your suggestion.
Thanks.

if(i == len)
{
i = -1;
}

(b) here is a way to write it without break:

Is break not recommended, or will it do harm to code, style, logic ..
etc. ?

int lookup(val, const int array[], int len)
{
int i = -1;
if(array != NULL && len != 0)
{
while(i < len && val != array)
{
++i;
}
if(i == len)
{
i = -1;
}
}
return i;
}

 

[cp]

You should never use break to escape from a if-check. That constitutes bad
programming.

lovecreatesbeauty said:

Any comments are welcome for following the two sequential search C
functions of both integer and string versions. Though they are simple,
please do not laugh at it Could you give your great suggestion to
it? Thanks a lot.

/*sequentially search a array of integers for a value. val: the integer
is to be searched for in the array, array: array of integers, len: item
count in the array. return the index of the value found in array, -1
for failure. the algotithm efficience of the function is O(n). - jhl,
Jul 2006*/

#include <stddef.h>

int lookup(int val, const int array[], int len)
{
int i = -1;

if (array != NULL && len != 0){
for (i = 0; i < len; ++i){
if (val == array){
break;
}
}
}
return i;
}

(a) either you should warn your users that a return value of len means "not
found", or you should add a check before the return:

Oh, len is out of range of the array. But I take your suggestion.
Thanks.

if(i == len)
{
i = -1;
}

(b) here is a way to write it without break:

Is break not recommended, or will it do harm to code, style, logic ..
etc. ?

int lookup(val, const int array[], int len)
{
int i = -1;
if(array != NULL && len != 0)
{
while(i < len && val != array)
{
++i;
}
if(i == len)
{
i = -1;
}
}
return i;
}

 

[Robert Gamble]

*Top Posting Fixed*

lovecreatesbeauty said:

Any comments are welcome for following the two sequential search C
functions of both integer and string versions. Though they are simple,
please do not laugh at it Could you give your great suggestion to
it? Thanks a lot.

/*sequentially search a array of integers for a value. val: the integer
is to be searched for in the array, array: array of integers, len: item
count in the array. return the index of the value found in array, -1
for failure. the algotithm efficience of the function is O(n). - jhl,
Jul 2006*/

#include <stddef.h>

int lookup(int val, const int array[], int len)
{
int i = -1;

if (array != NULL && len != 0){
for (i = 0; i < len; ++i){
if (val == array){
break;
}
}
}
return i;
}

(a) either you should warn your users that a return value of len means "not
found", or you should add a check before the return:

Oh, len is out of range of the array. But I take your suggestion.
Thanks.

if(i == len)
{
i = -1;
}

(b) here is a way to write it without break:

Is break not recommended, or will it do harm to code, style, logic ..
etc. ?

You should never use break to escape from a if-check. That constitutes bad
programming.

Please don't top post, it's not appreciated here.

I don't know what an "if-check" is, much less how to escape from one.
I assume you mean "You should never use break to break out of an if
statement" but that doesn't make any sense since you can't break out of
an if-statement, break only breaks out of case and loop statements, so
I don't understand what your point is. If you mean something else,
please clarify.

Robert Gamble

 

[pete]

lovecreatesbeauty wrote:

int slookup(const char *word, const char *array[], int len)

size_t len

would be better.

int main(void)
{
const char *word = "word";
const char *array[] = {"word", "at", "begining", "of", "array"};

if (slookup(word, array, (int)(sizeof array / sizeof *array)) != -1)
{
puts(word);
}
return 0;
}

 

[Richard Heathfield]

pete said:

int slookup(const char *word, const char *array[], int len)

size_t len

would be better.

Fine by me, but note the knock-on effect - it would then be better to make i
into a size_t too, and return a size_t, and then what happens to your -1
return for errors? Will you make it (size_t)-1?

 

[Joe Wright]

lovecreatesbeauty said:

Any comments are welcome for following the two sequential search C
functions of both integer and string versions. Though they are simple,
please do not laugh at it Could you give your great suggestion to
it? Thanks a lot.

/*sequentially search a array of integers for a value. val: the integer
is to be searched for in the array, array: array of integers, len: item
count in the array. return the index of the value found in array, -1
for failure. the algotithm efficience of the function is O(n). - jhl,
Jul 2006*/

#include <stddef.h>

int lookup(int val, const int array[], int len)
{
int i = -1;

if (array != NULL && len != 0){
for (i = 0; i < len; ++i){
if (val == array){
break;
}
}
}
return i;
}

(a) either you should warn your users that a return value of len means "not
found", or you should add a check before the return:

Oh, len is out of range of the array. But I take your suggestion.
Thanks.

if(i == len)
{
i = -1;
}

(b) here is a way to write it without break:

Is break not recommended, or will it do harm to code, style, logic ..
etc. ?

int lookup(val, const int array[], int len)
{
int i = -1;
if(array != NULL && len != 0)
{
while(i < len && val != array)
{
++i;
}
if(i == len)
{
i = -1;
}
}
return i;
}

Using break; is ugly. Consider..

int lookup(int val, const int array[], int len)
{
int i, ret = -1;
if (array != NULL && len > 0) {
for (i = 0; i < len; ++i) {
if (val == array) {
ret = i; /* set the return value */
i = len; /* kill the for loop */
}
}
}
return ret;
}

If val is not found we return -1.

 

[August Karlstrom]

Using break; is ugly. Consider..

int lookup(int val, const int array[], int len)
{
int i, ret = -1;
if (array != NULL && len > 0) {
for (i = 0; i < len; ++i) {
if (val == array) {
ret = i; /* set the return value */
i = len; /* kill the for loop */
}
}
}
return ret;
}

I think a while-loop is even clearer:

int lookup(int val, const int array[], int len)
{
int i, ret = -1;
if (array != NULL && len > 0) {
i = 0;
while ((i < len) && (val != array)) {
i++;
}
if (val == array) {
ret = i;
}
}
return ret;
}


August

 

[Eric Sosman]

lovecreatesbeauty said:

Any comments are welcome for following the two sequential search C
functions of both integer and string versions. Though they are simple,
please do not laugh at it Could you give your great suggestion to
it? Thanks a lot.

/*sequentially search a array of integers for a value. val: the integer
is to be searched for in the array, array: array of integers, len: item
count in the array. return the index of the value found in array, -1
for failure. the algotithm efficience of the function is O(n). - jhl,
Jul 2006*/

#include <stddef.h>

int lookup(int val, const int array[], int len)
{
int i = -1;

if (array != NULL && len != 0){
for (i = 0; i < len; ++i){
if (val == array){
break;
}
}
}
return i;
}

(a) either you should warn your users that a return value of len
means "not
found", or you should add a check before the return:

Oh, len is out of range of the array. But I take your suggestion.
Thanks.

if(i == len)
{
i = -1;
}

(b) here is a way to write it without break:

Is break not recommended, or will it do harm to code, style, logic ..
etc. ?

int lookup(val, const int array[], int len)
{
int i = -1;
if(array != NULL && len != 0)
{
while(i < len && val != array)
{
++i;
}
if(i == len)
{
i = -1;
}
}
return i;
}

Using break; is ugly. Consider..

int lookup(int val, const int array[], int len)
{
int i, ret = -1;
if (array != NULL && len > 0) {
for (i = 0; i < len; ++i) {
if (val == array) {
ret = i; /* set the return value */
i = len; /* kill the for loop */
}
}
}
return ret;
}

Ugliness is in the eye of the beholder, but this strikes
my eye as a good deal uglier than using a break, or even than
using a return from the middle of the loop. What I find most
objectionable is the "distributed knowledge" of the loop's
termination condition: The crucial assignment inside the if
depends on the precise details of the test in the for, and if
either gets changed without a matching change in the other, the
code stops working. (The comment helps, but ...)

Another problem is that this pattern doesn't generalize
easily to other loops. Using a linked list instead of an
array, the sequential search might be written

for (ptr = head; ptr != NULL; ptr = ptr->next) {
if (ptr->payload == value) {
/* what goes here? */
}
}

It doesn't seem to me that there's any assignment similar to
i = len (or len = i, for that matter) that would terminate the
loop as in the first example. My vote for "what goes here?"
would be a break: unobjectionable, non-tricky, easily read.

 

[Eric Sosman]

Using break; is ugly. Consider..

int lookup(int val, const int array[], int len)
{
int i, ret = -1;
if (array != NULL && len > 0) {
for (i = 0; i < len; ++i) {
if (val == array) {
ret = i; /* set the return value */
i = len; /* kill the for loop */
}
}
}
return ret;
}

I think a while-loop is even clearer:

int lookup(int val, const int array[], int len)
{
int i, ret = -1;
if (array != NULL && len > 0) {
i = 0;
while ((i < len) && (val != array)) {
i++;
}
if (val == array) {
ret = i;
}
}
return ret;
}

It might be clearer, but it's also wrong. On any
unsuccessful search, the loop terminates with i==len.
Then the test val==array gives undefined behavior due
to the out-of-bounds array index.

 

[Richard Heathfield]

Eric Sosman said:

Joe Wright wrote:

Using break; is ugly. Consider..

int lookup(int val, const int array[], int len)
{
int i, ret = -1;
if (array != NULL && len > 0) {
for (i = 0; i < len; ++i) {
if (val == array) {
ret = i; /* set the return value */
i = len; /* kill the for loop */
}
}
}
return ret;
}

Ugliness is in the eye of the beholder, but this strikes
my eye as a good deal uglier than using a break,

For the beautiful version, see my earlier reply.

 

[pete]

pete said:

int slookup(const char *word, const char *array[], int len)

size_t len

would be better.

Fine by me, but note the knock-on effect
- it would then be better to make i
into a size_t too, and return a size_t,
and then what happens to your -1
return for errors? Will you make it (size_t)-1?

Sure.
((size_t)-1), isn't a valid index
for an element in array that has ((size_t)-1) elements.

 

[Richard Heathfield]

pete said:

Richard Heathfield wrote:

[...] and then what happens to your -1
return for errors? Will you make it (size_t)-1?

Sure.
((size_t)-1), isn't a valid index
for an element in array that has ((size_t)-1) elements.

Excellent point.

 

[Keith Thompson]

Any comments are welcome for following the two sequential search C
functions of both integer and string versions. Though they are simple,
please do not laugh at it Could you give your great suggestion to
it? Thanks a lot.

/*sequentially search a array of integers for a value. val: the integer
is to be searched for in the array, array: array of integers, len: item
count in the array. return the index of the value found in array, -1
for failure. the algotithm efficience of the function is O(n). - jhl,
Jul 2006*/

#include <stddef.h>

int lookup(int val, const int array[], int len)
{
int i = -1;

if (array != NULL && len != 0){
for (i = 0; i < len; ++i){
if (val == array){
break;
}
}
}
return i;
}

Here's how I might write it (I haven't tested this):

int lookup(int val, const int array[], int len)
{
int i;
for (i = 0; i < len; i ++) {
if (array == val) {
return i;
}
}
return -1;
}

Notes:

I don't bother checking whether array == NULL; I'd document the
requirement and leave it up to the caller to get it right. If you
want to add the check, it's easy enough to do -- but it's not clear
that not finding the value in the array and not having a valid array
in the first place should yield the same result. Your problem
requirement doesn't address this one way or the other; it needs to.

I probably wouldn't use the "const int array[]" notation; instead, I
prefer the exactly equivalent "const int *array".

I'd probably also use size_t rather than int. This raises the issue
of how to indicate a failure. (size_t)-1 is a perfectly valid
possibility. Or you can return len, which is guaranteed not to be a
valid index.

 

[Al Balmer]

Using break; is ugly. Consider..

int lookup(int val, const int array[], int len)
{
int i, ret = -1;
if (array != NULL && len > 0) {
for (i = 0; i < len; ++i) {
if (val == array) {
ret = i; /* set the return value */
i = len; /* kill the for loop */
}
}
}
return ret;
}

Different strokes, I guess. I find the break less ugly. In fact, not
being quite so uptight about multiple returns in tiny functions, I'd
probably write (untested)

int lookup(int val, const int array[], int len)
{
int i;
if (array != NULL && len > 0) {
for (i = 0; i < len; ++i) {
if (val == array) {
return i;
}
}
}
return -1;
}

 

[Keith Thompson]

Different strokes, I guess. I find the break less ugly. In fact, not
being quite so uptight about multiple returns in tiny functions, I'd
probably write (untested)

int lookup(int val, const int array[], int len)
{
int i;
if (array != NULL && len > 0) {
for (i = 0; i < len; ++i) {
if (val == array) {
return i;
}
}
}
return -1;
}

In this version, the "&& len > 0" is redundant. If len == 0, the loop
won't execute, and you'll fall through to the "return -1;". (The
check was necessary in the original version, I think -- which is one
reason why yours is an improvement.)

 

[lovecreatesbeauty]

I don't bother checking whether array == NULL; I'd document the
requirement and leave it up to the caller to get it right. If you
want to add the check, it's easy enough to do -- but it's not clear
that not finding the value in the array and not having a valid array
in the first place should yield the same result. Your problem
requirement doesn't address this one way or the other; it needs to.

Thank you. I read Brian W. Kernighan and Rob Pike's `the practice of
programming'. In Section 4.8, they mentioned "defensive programming"
(sorry, I do not have a original English version and try to translate
it from Chinese version, so I do not exactly know if I express it
correctly). They (the book) convince me to do check for array
subscription, NULL pointer, ... (all bad conditions that should be
avoided) ...

I keep that additional check and change it from ( ... && len != 0) to (
.... && len > 0), it reassures me. The element count in an array should
be larger than zero, or I think it is better to stop it as soon as
possible in the program and do not let it move one more step. And my
revised version attached

/*lookup.c*/
#include <stddef.h>
int lookup(int val, const int array[], int len){
int i = -1;

if (array != NULL && len > 0){
for (i = 0; i < len; ++i){
if (val == array){
break;
}
}

if (i == len){
i = -1;
}
}
return i;
}

lovecreatesbeauty

 

[Keith Thompson]

Thank you. I read Brian W. Kernighan and Rob Pike's `the practice of
programming'. In Section 4.8, they mentioned "defensive programming"
(sorry, I do not have a original English version and try to translate
it from Chinese version, so I do not exactly know if I express it
correctly). They (the book) convince me to do check for array
subscription, NULL pointer, ... (all bad conditions that should be
avoided) ...

Fair enough -- but if you're going to check for a condition, you still
need to decide how you're going to handle it. For a search function,
I tend to think of not finding the value as a normal result, while
passing in a null pointer is an exceptional condition.

The important thing, IMHO, is to rigorously define the requirements
for your function. (That can include saying that the behavior is
undefined if you give it a null pointer; in that case, you can still
check for a null pointer if you choose.)

I keep that additional check and change it from ( ... && len != 0) to (
... && len > 0), it reassures me. The element count in an array should
be larger than zero, or I think it is better to stop it as soon as
possible in the program and do not let it move one more step. And my
revised version attached

/*lookup.c*/
#include <stddef.h>
int lookup(int val, const int array[], int len){
int i = -1;

if (array != NULL && len > 0){
for (i = 0; i < len; ++i){
if (val == array){
break;
}
}

if (i == len){
i = -1;
}
}
return i;
}

It looks correct as far as I can tell, but I find it more complex than
it needs to be. The main reason, I think, is that the variable i is
playing two different roles: it's the index as you step through the
array, and it's the value you return from the function. You have to
do some extra work (if (i == len) { i = -1; }) to make this work.

By using break, you're jumping out of the normal flow of control.
(Some people would object to that; I don't.) But as long as you're
doing that, why not just return from the function? Your break
statement breaks out of the loop and leaves it up to the following
code to figure out and return the correct value from the function --
but at the point where you do the break, you already know the value to
be returned.

In other words, rather than this:

if (val == array) {
break;
}

I'd write this:

if (val == array) {
return i;
}

That way, if you find the value in the array, you immediately return
the correct index. And if you finish the loop without having executed
the return statement, you know you haven't found the value in the
array, and you can return -1 directly rather than playing around with
the value of i -- and you don't need to initialize i to -1 at the top
of the function.

Applying my advice to your code (which, of course, you're entirely
free to ignore), we get this (not tested):

/*lookup.c*/
#include <stddef.h>
int lookup(int val, const int array[], int len){
int i;

if (array != NULL && len > 0){
for (i = 0; i < len; ++i){
if (val == array){
return i;
}
}
}
return -1;
}

 

[Richard Heathfield]

lovecreatesbeauty said:

I don't bother checking whether array == NULL [...]

Thank you. I read Brian W. Kernighan and Rob Pike's `the practice of
programming'. In Section 4.8, they mentioned "defensive programming"
(sorry, I do not have a original English version and try to translate
it from Chinese version, so I do not exactly know if I express it
correctly). They (the book) convince me to do check for array
subscription, NULL pointer, ... (all bad conditions that should be
avoided) ...

They're right. Keith's right too. That's the problem - it's a judgement
call.

I prefer to keep the checks in place. After all, the only plausible reason I
can think of for omitting the check is performance. And if parameter
validation is your bottleneck, you are a very lucky bunny indeed.