Fixed
>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.
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.
that line right there is making my index go out of bounds ... I dont really understand what is wrong with this though ...Code:midPtr = ( (leftPtr - *kennel) + (rightPtr - *kennel)) / 2 + *kennel;
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:
Here is my output: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; }
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
I hope this clears up any confusion. Sorry for being so dense before. Sometimes I miss the most obvious thingsCode:#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; }
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
so the high, low and mid should be of the same type as array.Code:int findValue(Bob **array, const int size, const int value)
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.
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 .. I need to get some stuff straight first ... so we'll start at step one
given:Code:int findDog(DogType * const kennel[], int numDogs, const String target) { DogType * leftPtr = kennel; // does not work
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]?
you need a pointer to a pointer you even said it.a pointer that points to kennel which points to kennel[0]?now look at Thantos's codeCode:DogType * leftPtr = kennel;[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]Code:Bob **low = array;
Last edited by linuxdude; 07-02-2004 at 12:18 PM.
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.
Bubble sort = quick and easy to implament and since the sample was small there was no real need to implament a better sortIs their anything better than that bubble sort you have.
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.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
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); }
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 ...