By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
431,795 Members | 1,250 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 431,795 IT Pros & Developers. It's quick & easy.

Comments are welcome for two sequential search C functions

P: n/a
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[i]){
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[i]) == 0){
break;
}
}
}
return i;
}

Jul 9 '06 #1
Share this Question
Share on Google+
31 Replies


P: n/a
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[i]){
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])
{
++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[i]) == 0){
break;
}
}
}
return i;
}
Ditto, on all counts.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Jul 9 '06 #2

P: n/a
Richard Heathfield wrote:
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[i]){
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])
{
++i;
}
if(i == len)
{
i = -1;
}
}
return i;
}
Jul 9 '06 #3

P: n/a
cp
You should never use break to escape from a if-check. That constitutes bad
programming.

"lovecreatesbeauty" <lo***************@gmail.comwrote in message
news:11*********************@b28g2000cwb.googlegro ups.com...
Richard Heathfield wrote:
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[i]){
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])
{
++i;
}
if(i == len)
{
i = -1;
}
}
return i;
}

Jul 9 '06 #4

P: n/a
*Top Posting Fixed*

cp wrote:
"lovecreatesbeauty" <lo***************@gmail.comwrote in message
news:11*********************@b28g2000cwb.googlegro ups.com...
Richard Heathfield wrote:
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[i]){
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

Jul 9 '06 #5

P: n/a
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;
}

--
pete
Jul 9 '06 #6

P: n/a
pete said:
lovecreatesbeauty wrote:
>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?

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Jul 9 '06 #7

P: n/a
lovecreatesbeauty wrote:
Richard Heathfield wrote:
>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[i]){
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])
{
++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[i]) {
ret = i; /* set the return value */
i = len; /* kill the for loop */
}
}
}
return ret;
}

If val is not found we return -1.

--
Joe Wright
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
Jul 9 '06 #8

P: n/a
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[i]) {
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])) {
i++;
}
if (val == array[i]) {
ret = i;
}
}
return ret;
}
August
Jul 9 '06 #9

P: n/a
Joe Wright wrote:
lovecreatesbeauty wrote:
>Richard Heathfield wrote:
>>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[i]){
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])
{
++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[i]) {
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
es*****@acm-dot-org.invalid
Jul 9 '06 #10

P: n/a
August Karlstrom wrote:
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[i]) {
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])) {
i++;
}
if (val == array[i]) {
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[i] gives undefined behavior due
to the out-of-bounds array index.

--
Eric Sosman
es*****@acm-dot-org.invalid

Jul 9 '06 #11

P: n/a
Eric Sosman said:
Joe Wright wrote:
<snip>
>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[i]) {
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. :-)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Jul 9 '06 #12

P: n/a
Richard Heathfield wrote:
>
pete said:
lovecreatesbeauty wrote:
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.

--
pete
Jul 9 '06 #13

P: n/a
pete said:
Richard Heathfield wrote:
<snip>
>>
[...] 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. :-)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Jul 9 '06 #14

P: n/a
"lovecreatesbeauty" <lo***************@gmail.comwrites:
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[i]){
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[i] == 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.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Jul 9 '06 #15

P: n/a
On Sun, 09 Jul 2006 09:46:12 -0400, Joe Wright
<jo********@comcast.netwrote:
>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[i]) {
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[i]) {
return i;
}
}
}
return -1;
}

--
Al Balmer
Sun City, AZ
Jul 9 '06 #16

P: n/a
Al Balmer <al******@att.netwrites:
[...]
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[i]) {
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.)

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Jul 9 '06 #17

P: n/a
Keith Thompson wrote:
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[i]){
break;
}
}

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

lovecreatesbeauty

Jul 10 '06 #18

P: n/a
"lovecreatesbeauty" <lo***************@gmail.comwrites:
Keith Thompson wrote:
>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) ...
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[i]){
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[i]) {
break;
}

I'd write this:

if (val == array[i]) {
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[i]){
return i;
}
}
}
return -1;
}

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Jul 10 '06 #19

P: n/a
lovecreatesbeauty said:
Keith Thompson wrote:
>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.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Jul 10 '06 #20

P: n/a
Eric Sosman wrote:
August Karlstrom wrote:
>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[i]) {
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])) {
i++;
}
if (val == array[i]) {
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[i] gives undefined behavior due
to the out-of-bounds array index.
Yes, of course. How careless of me. It should be:

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])) {
i++;
}
if (i < len) {
ret = i;
}
}
return ret;
}
August
Jul 10 '06 #21

P: n/a
Keith Thompson wrote:
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[i]){
return i;
}
}
}
return -1;
}
I have heard that multiple exit points makes function inline
optimization more difficult. If that is the case, the use of a result
variable might be a better choice.
August
Jul 10 '06 #22

P: n/a
August Karlstrom wrote:
Keith Thompson wrote:
>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[i]){
return i;
}
}
}
return -1;
}

I have heard that multiple exit points makes function inline
optimization more difficult. If that is the case, the use of a result
variable might be a better choice.
They can also cause logic errors if the setting of a state gets missed,
releasing a lock for example

--
Ian Collins.
Jul 10 '06 #23

P: n/a
August Karlstrom wrote:
Keith Thompson wrote:
>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[i]){
return i;
}
}
}
return -1;
}

I have heard that multiple exit points makes function inline
optimization more difficult. If that is the case, the use of a result
variable might be a better choice.
First rule of optimisation: Don't do it.
Second rule (for experts only): Don't do it yet.

Unless you have measured and found this to be a problem, use the
solution that is easier to implement correctly and easier to maintain.
Some people might choose the single exit for that reason, some might
choose the multiple exit for that reason.

In any case, this is a common enough idiom that I would be surprised if
optimisers did not handle it well.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc
Jul 10 '06 #24

P: n/a
Richard Heathfield wrote:
(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])
And this won't try to access array[-1] ? Just goes to show, even the
most experience programmers are not immune to buffer overflows.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

Jul 10 '06 #25

P: n/a
we******@gmail.com said:
Richard Heathfield wrote:
>(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])

And this won't try to access array[-1] ?
Ouch! Nice spot.

Fortunately for my peace of mind, in my own code I clearly separate the
concepts of "output data" and "error information". The above boo-boo is a
result of trying to combine them.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Jul 10 '06 #26

P: n/a
On Sun, 09 Jul 2006 21:13:47 GMT, Keith Thompson <ks***@mib.org>
wrote:
>Al Balmer <al******@att.netwrites:
[...]
>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[i]) {
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;".
(Or len < 0) Quite true, of course. I just replaced the inner loop. In
real life, I'd look a little closer, especially since the
non-idiomatic style of the original would indicate (in my environment)
a less experienced programmer.
(The
check was necessary in the original version, I think -- which is one
reason why yours is an improvement.)
--
Al Balmer
Sun City, AZ
Jul 10 '06 #27

P: n/a
On Mon, 10 Jul 2006 11:08:40 GMT, August Karlstrom
<fu********@comhem.sewrote:
>Keith Thompson wrote:
>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[i]){
return i;
}
}
}
return -1;
}

I have heard that multiple exit points makes function inline
optimization more difficult. If that is the case, the use of a result
variable might be a better choice.
<GI don't write code based on rumors about hardship for compilers.

--
Al Balmer
Sun City, AZ
Jul 10 '06 #28

P: n/a
Richard Heathfield <in*****@invalid.invalidwrote:
lovecreatesbeauty said:
>Any comments are welcome for following the two sequential search C
<snip>
>#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[i]){
break;
}
}
}
return i;
}
<snip>
(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])
{
++i;
}
if(i == len)
{
i = -1;
}
}
return i;
}
This has one of the worst kinds of UB as it will run correctly on a
wide range of systems and you probably won't even *smell* a dragon --
it just might report, sometimes, that an element is "not there" when in
fact it is.

You need, of course, to set i to 0 before asking about array[i] for
the first time (and to give a type for "val").

--
Ben.
Jul 10 '06 #29

P: n/a
Ben Bacarisse said:
Richard Heathfield <in*****@invalid.invalidwrote:
<a very silly bug>
This has one of the worst kinds of UB
I know, I know - very embarrassing and all that. Would you believe me if I
told you my personal code library doesn't do things that way? :-)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Jul 10 '06 #30

P: n/a
Richard Heathfield wrote:
Ben Bacarisse said:
>Richard Heathfield <in*****@invalid.invalidwrote:

<a very silly bug>
>This has one of the worst kinds of UB

I know, I know - very embarrassing and all that. Would you believe me if I
told you my personal code library doesn't do things that way? :-)
Richard Heathfield wrote (in thread "Inflexible array members"):
Just as I wouldn't criticise my wife for failing to tell me to fasten my
seatbelt, so I don't criticise my compiler for failing to tell me about
buffer overruns. Remembering to fasten my seatbelt is /my/ job, and I can
take care of it myself, but of course someone needs to keep an eye on the
kids in the back. Avoiding buffer overruns is /my/ job, and I can take care
of it myself, but of course someone needs to keep an eye on the Java kids
in the back.
You're not one of those kids in the back, are you? ;-)

Sorry for being such a pain in the behind. Just couldn't help myself.
August
Jul 10 '06 #31

P: n/a
August Karlstrom said:
Richard Heathfield wrote:
>Ben Bacarisse said:
>>Richard Heathfield <in*****@invalid.invalidwrote:

<a very silly bug>
>>This has one of the worst kinds of UB

I know, I know - very embarrassing and all that. Would you believe me if
I told you my personal code library doesn't do things that way? :-)

Richard Heathfield wrote (in thread "Inflexible array members"):
All right, all right! I KNOW! I KNOW!

It was my job to check that the code was correct before I posted it, and I
failed to do that. This is now the third time I have acknowledged the fact.
What do you want, sack-cloth and ashes? :-)

If anything, this little incident does help to show why comp.lang.c is such
a valuable resource. The code reviews are first-class, and nobody is immune
from them. That's a Good Thing, even (or perhaps /especially/) when it
bites a reg.

But can we drop it now, please?

<snip>
Sorry for being such a pain in the behind. Just couldn't help myself.
Don't worry about it. I'll get you the next time. :-)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Jul 11 '06 #32

This discussion thread is closed

Replies have been disabled for this discussion.