bsearch return NULL but the element is in the array

Question

#define u32 uint32_t
#define Narray 10

struct edge {
  u32 v1;
  u32 v2;
};
int struct_cmp_by_v1(const void *i, const void *j) {
  struct edge *a = (struct edge *)i;
  struct edge *b = (struct edge *)j;
  u32 x = a->v1;
  u32 y = b->v1;
  return x > y ? 1 : -1;
}
struct edge *array = malloc((sizeof(struct edge))*Narray);
struct edge *l = malloc(sizeof(struct edge));
struct edge *e = (struct edge *) bsearch(l, array, Narray, sizeof(struct edge), struct_cmp_by_v1);

The array is small with large numbers u32 but I only look for an element according to a field of the ,struct edge, that is v1 then the comparison is only made between v1.

The key used by bsearch is, struct edge *l, where l->v1 contains the element to be searched.

The ,array of struct edge, has element v1 to find but bserach does not find it and return NULL, I do not see the error that I'm committing

Note: The array contains only 10 elements to test but it can be a very large array with 25056012 elements, even more

Your comparison function never returns 0, just -1 and +1. So it never tells `bsearch` it has found the item being sought. — Eric Postpischil, Apr 04 '18 at 23:34
Note: for a small array (N=10) linear search is probably optimal. — wildplasser, Apr 04 '18 at 23:56
The arrangement is 10 only to test but it can actually be a very large array with 25056012 elements, even more — Ivan Pereyra, Apr 05 '18 at 00:36
@wildplasser [Where to choose linear search over binary search](https://stackoverflow.com/q/22546024/995714), [At which n does binary search become faster than linear search on a modern CPU?](https://stackoverflow.com/questions/1275665/at-which-n-does-binary-search-become-faster-than-linear-search-on-a-modern-cpu) — phuclv, Apr 05 '18 at 01:08

John3136 · Answer 1 · 2018-04-05T00:50:41.393

1

return x > y ? 1 : -1; Never returns 0 (a match). Try return (int)(x - y); (just noted unsigned types so need to be aware of that - I've used a simple cast but there is likely a safer way)

Comment re: overflow is correct (but unlikely in normal usage), if on is a huge positive and the other is a huge negative then you're going to have problems.

A nice clear way to handle any size without overflow or sign issues:

if (x == y)
    return 0;
return x > y ? 1 : -1;

edited Apr 05 '18 at 00:50

answered Apr 04 '18 at 23:52

John3136

28,809
4
51
69

While subtraction works when the numbers are small, it risks overflow if the numbers are large. It isn't a good way to write a comparator. – Jonathan Leffler Apr 05 '18 at 00:21
the comparator that I need must support large unsigned int numbers, in this case it must support an unsigned 32-bit integer – Ivan Pereyra Apr 05 '18 at 00:45
@IvanPereyra Key point is you don't have a "return 0 if equal" case. Fix that and you're done. – John3136 Apr 05 '18 at 00:49

score 0 · Answer 2 · edited Apr 05 '18 at 17:21

0

Thanks for the answers, they helped me find the solution. I still do not probe it for a large array. Anyway, the comparison function is:

int struct_cmp_by_v2(const void *i, const void *j) {
  struct edge *a = (struct edge *)i;
  struct edge *b = (struct edge *)j;
  u32 x = a->v1;
  u32 y = b->v1;
  if (x == y)
    return 0;
  else {
    if (x > y)
      return 1;
    else
      return -1;
  }
}

edited Apr 05 '18 at 17:21

phuclv

37,963
15
156
475

answered Apr 05 '18 at 01:11

Ivan Pereyra

19
2

`return (x > y) - (x < y);` will be much simpler and there's no overflow whatsoever – phuclv Apr 05 '18 at 01:21
What you have there is likely to cause compiler warnings about the fn not returning a value since the returns are buried in elses. I'd refactor to `if (x != y) { ... } return 0;` – John3136 Apr 05 '18 at 01:48
1

@John3136: It is easy to see each case in the above returns a value. Can you cite any particular compiler and version which produces a warning for the code shown? – Eric Postpischil Apr 05 '18 at 16:07
@EricPostpischil - Easy for a person to see but not necessarily a compiler. You'll note I said warnings - not errors. – John3136 Apr 05 '18 at 22:35
@John3136: This is easy for a compiler to see. In analyzing the source, compilers construct graphs (or other structures) of potential control flow. In this case, where every branch contains a return, the graph shows no control flow reaching the end of the function. – Eric Postpischil Apr 05 '18 at 22:57
@EricPostpischil We'll have to agree to disagree. I'm not going to try it on all the ancient compilers I currently have to use. Pretty sure one of the older solaris C compilers flags this. Perhaps I'll flip my comment. Perhaps the compiler can tell, but in a 1000+ line function (the joys of legacy code) the maintainer will have a lot of work to check ;-) – John3136 Apr 05 '18 at 23:10

bsearch return NULL but the element is in the array

2 Answers2

Linked