Thread: Binary search of an array of pointers to structs using pointer arithmetic

I think it has more to do with your control then with the line itself.

I think you should read Preludes post in which she outlines the algo for binary search. The one you have posted does not follow that and in reality it should.

And which way is it going out of bounds? To far in the postive direction or too far in the negitive direction?

I had changed my code .. here is a copy of my updated code:

Code:

int findDog(DogType * const kennel[], int numDogs, const String target) {
	DogType * leftPtr = (DogType*)malloc(sizeof(DogType));
	DogType * rightPtr = (DogType*)malloc(sizeof(DogType));
	DogType * midPtr = (DogType*)malloc(sizeof(DogType));
	
	leftPtr = * kennel;
	rightPtr = *(kennel + numDogs - 1);
	
	while (leftPtr <= rightPtr) {
		midPtr = ( (leftPtr - *kennel) + (rightPtr - *kennel)) / 2 + *kennel;		
		
		fprintf(stderr, "%s ", leftPtr -> dogName); // a check - prints correctly
		fprintf(stderr, "%s ", rightPtr -> dogName); // a check - prints correctly
		fprintf(stderr, "%s ", midPtr -> dogName); // a check - returns null
		
		if(strcmp(midPtr -> dogName, target) < 0)
			leftPtr = midPtr + 1;
		
		else if(strcmp(midPtr -> dogName, target) > 0)
			rightPtr = midPtr - 1;
		
		else
			return midPtr - *kennel;
	}
	
	return -1;
	
}

Here is my output:

Bill Tommy (null) Segmentation fault

Ok I'm getting a little tired of the running in circles (part of which is my fault). Here is a sample code I wrote to do eactly what want. Only difference is that you'll have to use strcmp() instead of a stright equality check

Code:

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

typedef struct {
  int value;
}Bob;

int myrandom(int max) {
  return (int)( ((float)rand() / RAND_MAX ) * max );
}

int findValue(Bob *[], const int, const int);

int main()
{
  int i,j, index;
  Bob *array[10], *temp;

  for (i=0; i < 10; i++)
    array[i] = malloc(sizeof(Bob));

  for (i=0; i < 9; i++)
    array[i]->value = myrandom(20);
  array[9]->value = 12;

  for (i=0; i < 9; i++)
    for (j=i+1; j<10; j++)
      if ( array[i]->value > array[j]->value )
      {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }

  index = findValue(array, 10, 12);
  if ( index == -1 )
    puts("Could not find that value");
  else
    printf("Found the value at index %d which has the value of %d\n", index, array[index]->value);

  for (i=0; i<10; i++)
    free(array[i]);

  return 0;
}

int findValue(Bob *array[], const int size, const int value) {
  Bob **low = array;
  Bob **high = array + size -1;
  Bob **mid = ((low-array)+(high-array)) / 2 + array;

  while ( high > low )
  {
    if ( (*mid)->value == value )
      return mid - array;

    if ( (*mid)->value > value )
    {
      high = mid - 1;
      mid = ((low-array)+(high-array)) / 2 + array;
    }

    if ( (*mid)->value < value )
    {
      low = mid + 1;
      mid = ((low-array)+(high-array)) / 2 + array;
    }

  }
  return -1;
}

I hope this clears up any confusion. Sorry for being so dense before. Sometimes I miss the most obvious things

You pass a pointer to a struct and naturally ** is a pointer to a pointer, then it assigned it to the memory address of the pointer array.
[edit]Good code Thantos clear and consise. Is their anything better than that bubble sort you have. And how did you beat me on that response [/edit]

okay .. first off, I am sorry for making this a super long drawn out process :\

Your code worked great .. but when I translated your code into mine, I got a segmentation fault (again when trying to print out mid -> value) and also warnings when I compiled. (warning: initialization discards qualifiers from pointer target type).

I do have one question however, what does Bob **low = array; do?

well it shouldn't be mid->value it should be (*mid)->value if you are following my code.

And don't feel bad I'm as much to blame as you are

the reason I used Bob **low = array was because array itself is really a pointer to a pointer to a structure called Bob. The function header could easy be rewritten as

Code:

int findValue(Bob **array, const int size, const int value)

so the high, low and mid should be of the same type as array.

As for the "(warning: initialization discards qualifiers from pointer target type)" its just because you have array as a const and high, low, and mid are not so its a possible problem.

okay .. I need to get some stuff straight first ... so we'll start at step one

Code:

int findDog(DogType * const kennel[], int numDogs, const String target) {	
	DogType * leftPtr = kennel; // does not work

given:
kennel is an array of pointers that point to DogTypes.

I am creating leftPtr which is a DogType pointer, (not an actual DogType, but a instead just a pointer to a DogType). kennel is actually just a pointer to an array and it actually points to kennel[0] (right?). So when I say DogType * leftPtr = kennel ... why doesnt it create a pointer that points to kennel which points to kennel[0]?

OMG!

It just clicked ... like you said, I had even said it myself ... kennel is just a pointer to an array of Dogs. I want to create a pointer that points to a pointer. We havnt gotten to that in class yet so I had no idea what you guys were talking about. I totally understand this way now and all the syntax ...

Now I have to go back and butcher my code so that it doesn use a ** leftPtr, cause I dont know if I will get credit for using that.

Thank you guys so much, I am sorry for being a major pain in everybodies side.

Is their anything better than that bubble sort you have.

Bubble sort = quick and easy to implament and since the sample was small there was no real need to implament a better sort

Another one for Thantos, why such a excessive rand function? Using floats then coercing them to ints; I don't know why? To have a one line for loop

Because rand() returns an int and RAND_MAX is an int so if you don't promote one of them to float when you do the division you'll get 0 everytime. Search the board and you'll see better ways for sorting and random but like I said, I was going for something I could throw together to setup the data in a way that shows what needed to be done in the function accuratly.

assuming this is from the function that Thantos provided, are these two statements the same?

Bob **low = array;
Bob *low = *array;

I dont think they are ...

No they are not the same.

The first one is a pointer to a pointer to a structure which is assigned the same value as array
The second one is a pointer to a structure which is assigned the value of what array is pointing to.

Since array holds pointers to structures when need to use on more level of indirection when doing the search.

So if the array held integers you'd have int *.
If the array had pointers to pointers to pointers to pointers to structures (bob ****) we'd need to use bob *****. Having fun yet?

oh yeah .. this is gonna get real fun

Thanks for the quick reply ...

BTW .. is there another way of writing Bob **low = array;?

Bob **low = &array[0];