bsearch is returning different value.

[sharathr]

Hi All,

Please find the program where I'm passing key value '6' for searching in array of structures but it is returning 'The number is in the array cdng::8 grp_idx::1' as output. Can somebody please let me know what I'm doing wrong?

------------------------------------

#include <stdio.h>

struct grp_cdng
{
const int *cdng;
const int *grp_idx;
};

struct grp_cdng new_grp[] =
{
{6,0},
{7,3},
{8,1},
{9,3},
{13,2}
};

int count = sizeof(new_grp) / sizeof(struct grp_cdng);

int compare(const struct grp_cdng *one, const struct grp_cdng *two)
{
return one->cdng - two->cdng;
}

int main(void)
{
struct grp_cdng *search_me,search_key;

search_key.cdng = 6;

printf("before bsearch:\n");

search_me=bsearch(&search_key,new_grp,count,sizeof(struct grp_cdng),compare);

printf("after bsearch:\n");

if (search_me)
printf("The number is in the array cdng::%d grp_idx::%d\n",search_me->cdng,search_me->grp_idx);
else
printf("Couldn't find in array\n");
}
------------------------

Thanks,
Sharath.

 

[Salem]

Seems to work here, post edits. Check the /*!! comments.

#include <stdio.h>
#include <stdlib.h> /*!! added */

struct grp_cdng
{
  int cdng;   /*!! removed "pointer" - did it ever work for you? */
  int grp_idx;/*!! const doesn't help either - it prevents you assigning anything */
};

struct grp_cdng new_grp[] =
{
  {6,0},
  {7,3},
  {8,1},
  {9,3},
  {13,2}
};

int count = sizeof(new_grp) / sizeof(struct grp_cdng);

int compare(const void *pa, const void *pb)
{
  const struct grp_cdng *one = pa;  /*!! cast to correct type inside the function */
  const struct grp_cdng *two = pb;  /*!! bsearch expects a function which takes void*'s */
  /*!! return one->cdng - two->cdng;     this potentially overflows!!! */
  if ( one->cdng > two->cdng ) {
    return +1;
  } else
  if ( one->cdng < two->cdng ) {
    return -1;
  } else {
    return 0;
  }
}

int main(void)
{
  struct grp_cdng *search_me,search_key;

  search_key.cdng = 6;

  printf("before bsearch:\n");

  search_me = bsearch ( &search_key,
                         new_grp,
                         sizeof(new_grp)/sizeof(new_grp[0]),
                         sizeof(new_grp[0]),
                         compare);

  printf("after bsearch:\n");

  if (search_me)
    printf("The number is in the array cdng::%d grp_idx::%d\n",
           search_me->cdng, search_me->grp_idx );
  else
    printf("Couldn't find in array\n");
  return 0; /*!! added */
}

Please use the [tt][ignore]

[/ignore][/tt] tags when posting code.

--

 

[sharathr]

Thanks Salem,

I have a situation where my array is having following values

struct grp_cdng new_grp[] =
{
{6,0},
{6,3},
{8,1},
{9,3},
{13,2}
};

when my key is 6, I would like to know following things:

1. The program should return 2(count) when I'm searching array with key value 6?

2. How to retrieve the values for these matched key values? It should return (6,1) and (6,3).

Thanks in advance.

Sharath.

 

[Salem]

Take the pointer you get back, then do a linear search forwards and backwards from that point counting as you go.


--

 

[sharathr]

Can you please give me some examples in my case how to do linear search.

Regards,
sharath.

 

[Salem]

I could, but you need to have a go at it first.


--

 

[sharathr]

I didn't understad how to get the position of the key in the array after it is returning pointer from bsearch.

I didn't want go each eliment in the array to compare the values returned from bsearch pointer.

Sharath.

 

[Salem]

Oh, you mean like
[tt]int pos = search_me - new_grp;[/tt]

--

 

[sharathr]

Example: array is as below

struct grp_cdng new_grp[] =
{
{6,0},
{6,3},
{8,1},
{8,3},
{13,2}
};


key is set to 8 so search_me is returning (8,1), I don't know which position this element is there(3rd) in the array?

I should not go each element in the array(0 to 5) to compare where (8,1) is present then doing linear search. This process will take long time in case my array is populated with 10000 rows.

Is there anyway we can know from search_me which position this element is present in the array?

--Sharath

 

[Salem]

Oh well

#include <stdio.h>
#include <stdlib.h>

struct grp_cdng
{
  int cdng;
  int grp_idx;
};

int compare(const void *pa, const void *pb)
{
  const struct grp_cdng *one = pa;
  const struct grp_cdng *two = pb;
  if ( one->cdng > two->cdng ) {
    return +1;
  } else
  if ( one->cdng < two->cdng ) {
    return -1;
  } else {
    return 0;
  }
}

int countMatches ( struct grp_cdng *array,
                   size_t arraysize,
                   struct grp_cdng *key,
                   int (*compare)(const void*, const void*) )
{
  struct grp_cdng *search_me;
  int              result = 0;

  search_me = bsearch ( key,
                        array,
                        arraysize,
                        sizeof(*array),
                        compare );
  if ( search_me ) {
    struct grp_cdng *lower = search_me;
    struct grp_cdng *upper = search_me;

    /* search back towards the start of the array */
    do {
      if ( lower > &array[0] ) lower--;
    } while ( compare(lower,key) == 0 && lower > &array[0] );
    if ( compare(lower,key) != 0 ) lower++;

    /* search forward */
    do {
      if ( upper < &array[arraysize-1] ) upper++;
    } while ( compare(upper,key) == 0 && upper < &array[arraysize-1] );
    if ( compare(upper,key) != 0 ) upper--;

    result = upper - lower + 1;
  } else {
    result = 0;
  }
  return result;
}

int main(int argc, char *argv[])
{
  struct grp_cdng new_grp[] =
  {
    {6,0},
    {7,3},
    {8,1},
    {8,2},
    {9,3},
    {13,2}
  };
  struct grp_cdng search_key;
  int             count;

  search_key.cdng = atoi(argv[1]);
  count = countMatches ( new_grp,
                         sizeof(new_grp)/sizeof(new_grp[0]),
                         &search_key,
                         compare );
  printf( "Key %d appears %d times\n", search_key.cdng, count );
  return 0;
}


$ ./a.out 6 ; ./a.out 8 ; ./a.out 13 ; ./a.out 42
Key 6 appears 1 times
Key 8 appears 2 times
Key 13 appears 1 times
Key 42 appears 0 times

> I don't know which position this element is there(3rd) in the array?
I showed you how to turn a pointer into an index, but apparently you didn't understand.
If you have [tt]int array[10]; int *p = &array[3];[/tt]
Then [tt]p - array[/tt] will be 3.

> This process will take long time in case my array is populated with 10000 rows.
But the whole point of bsearch is that the array is sorted, so that all the 8's say are together. You only need look back and forward until you find something which isn't 8 (or the ends of the array).
It's only going to take a long time if you consider most of your records to be identical.

--

 

[sharathr]

Thanks Salem.