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

  1. #16
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Fixed

  2. #17
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >why is using pointer arithmetic bad?
    The unwashed masses tend to break things when they use pointer arithmetic. It's a particularly hairy and error prone area of C that should be avoided whenever possible. Simple arithmetic is fine, such as iterating over an array provided you check your boundaries, but anything more complex can be dicey unless you know exactly what you're doing and document it well.
    My best code is written with the delete key.

  3. #18
    Registered User
    Join Date
    Jun 2004
    Posts
    17
    you guys are awesome .. thanks for all the help so far .. but there is still one little kink in this algorithm. After all my 'I just woke up' editing and quick fixes (like mallocing memory .. noticing that (*leftPtr).dogName is the same as leftPtr -> dogName, etc) there is one line that is giving me trouble.

    Code:
    midPtr = ( (leftPtr - *kennel) + (rightPtr - *kennel)) / 2 + *kennel;
    that line right there is making my index go out of bounds ... I dont really understand what is wrong with this though ...

  4. #19
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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?

  5. #20
    Registered User
    Join Date
    Jun 2004
    Posts
    17
    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

  6. #21
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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

  7. #22
    Registered User
    Join Date
    Jun 2004
    Posts
    17
    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?

  8. #23
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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.

  9. #24
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    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]

  10. #25
    Registered User
    Join Date
    Jun 2004
    Posts
    17
    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]?

  11. #26
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    a pointer that points to kennel which points to kennel[0]?
    you need a pointer to a pointer you even said it.
    Code:
    DogType * leftPtr = kennel;
    now look at Thantos's code
    Code:
    Bob **low = array;
    [edit]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[/edit]
    Last edited by linuxdude; 07-02-2004 at 12:18 PM.

  12. #27
    Registered User
    Join Date
    Jun 2004
    Posts
    17
    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.

  13. #28
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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.

  14. #29
    .
    Join Date
    Nov 2003
    Posts
    307
    You could consider bsearch kinda like this:

    Code:
    struct node {                   /* these are stored in the table */
          char string[128];
          int length;
      };
    int node_compare(const void *, const void *);    
          
    int binary_search(struct node table[], const char *target, int nelems){
          struct node *node_ptr, node;
          int retval=0;
          int working=0;
          
          node_ptr = (struct node *)bsearch((void *)target,
                                            (void *)table, 
                                            TABSIZE,
                                            sizeof(struct node), 
                                            node_compare);
          if (node_ptr == NULL) {      
              retval=(-1);
          } else {
              working=(int)&table[0];    
              while( (int)node_ptr> working){
                     retval++;
                     working+=sizeof(struct node);
              }
          }
          return retval;
    }      
      
    int node_compare(const void *node1, const void *node2) {
          return strcmp(((const struct node *)node1)->string,
                      ((const struct node *)node2)->string);
    }

  15. #30
    Registered User
    Join Date
    Jun 2004
    Posts
    17
    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 ...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. sorting number
    By Leslie in forum C Programming
    Replies: 8
    Last Post: 05-20-2009, 04:23 AM
  2. Pointer to array of string and Array of Pointer to String
    By vb.bajpai in forum C Programming
    Replies: 2
    Last Post: 06-15-2007, 06:04 AM
  3. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 10:18 AM
  4. Array, Linked List, or Binary Tree?
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 01-05-2002, 10:07 PM
  5. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 09:48 AM