# Binary search of an array of pointers to structs using pointer arithmetic

Show 80 post(s) from this thread on one page
Page 1 of 4 1234 Last
• 07-01-2004
mgimbl
Binary search of an array of pointers to structs using pointer arithmetic
I have an array of structs and I want to B-Search these by a value inside of them. I am having trouble because I need to return the index (not address) after searching through the array of structs (typedef structs). This is what I have, and I am not sure my logic behind it is even right. Can somebody please help.

Code:

```int findValue(StructType * const array[], int size, const String target) {         StructType * leftPtr = * array;               StructType * rightPtr = (* array) + size - 1; // error for the + sign         StructType * midPtr;                 while (strcmp((*leftPtr).value, (*rightPtr).value) <= 0) {                        midPtr = (leftPtr + rightPtr) / 2;                                 while(strcmp((*midPtr).value, target) < 0) {                         leftPtr = midPtr + 1;                         midPtr = (leftPtr + rightPtr) / 2;                 }                                 if (strcmp((*midPtr).value, target) == 0)                         return midPtr - array;         }                 return -1;         }```
• 07-01-2004
Thantos
Given:
Code:

```int array[10]; int *p = array, index; /* some code that changes p */```
the easist way to get the index from the pointer is simply:
Code:

`index = p - array;`
• 07-01-2004
mgimbl
well that solved one of my big questions .. and I now know what I have to return, thanks.

But the other problem is I have StructType pointers and I need int pointers (I think) ..
See my return statement .. if I did :
Code:

`return midPtr - array;`
that would try to subtract two StructTypes instead of two ints ... see what I am saying?
• 07-01-2004
Thantos
you are right that the pointers themselves are of StructTypes but when you do the arithmatic on them the result is an integer.
• 07-01-2004
mgimbl
here are my errors when trying to compile that code above:

Code:

```[mgimbl@localhost project1]\$ make gcc -c kennel.c kennel.c: In function `findDog': kennel.c:55: error: invalid operands to binary + kennel.c:59: error: invalid operands to binary + kennel.c:63: error: invalid operands to binary - make: *** [kennel.o] Error 1```
• 07-01-2004
Thantos
Oh thats right you can not do addition between two pointers only subtraction.
Its fairly simple to get around:
Code:

`midPtr = ( (leftPtr-array) + (rightPtr-array)) / 2 + array;`
• 07-01-2004
mgimbl
sorry for being a major pain :)

same errors are still present after your last suggestion ...
I have linked my actual code.

Code:

```int findDog(DogType * const kennel[], int numDogs, const String target) {         DogType * leftPtr = * kennel;         DogType * rightPtr = (* kennel) + (numDogs - 1);         DogType * midPtr;                 while (strcmp((*leftPtr).dogName, (*rightPtr).dogName) <= 0) {                        midPtr = (leftPtr + rightPtr) / 2;                                 while(strcmp((*midPtr).dogName, target) < 0) {                         leftPtr = midPtr + 1;                         midPtr = (leftPtr + rightPtr) / 2 + kennel;                 }                                 if (strcmp((*midPtr).dogName, target) == 0)                         return midPtr - kennel;         }                 return -1;         }```
• 07-02-2004
Thantos
Like I said in the last post you can't add two pointers together. So
Code:

`midPtr = (leftPtr + rightPtr) / 2;`
should be
Code:

`midPtr = ( (leftPtr-kennel) + (rightPtr-kennel)) / 2 + kennel;`
• 07-02-2004
mgimbl
oh I am sorry ... I didnt update that piece of code ... these are my error now:

kennel.c: In function `findDog':
kennel.c:55: error: invalid operands to binary -
kennel.c:55: error: invalid operands to binary -
kennel.c:59: error: invalid operands to binary -
kennel.c:59: error: invalid operands to binary -
kennel.c:63: error: invalid operands to binary -
make: *** [kennel.o] Error 1

Still talking about me subtracting them ...
• 07-02-2004
anonytmouse
There is one golden rule with pointer arithmetic - "Don't use pointer arithmetic!".
Code:

```int findValue(StructType * const array[], size_t size, const String target) {         size_t mid_index  = 0;         size_t left_index  = 0;         size_t right_index = size - 1;         while (strcmp(array[left_index]->value, array[right_index]->value) <= 0)         {                 mid_index = (left_index + right_index) / 2;                 while(strcmp(array[mid_index]->value, target) < 0)                 {                         left_index = mid_index + 1;                         mid_index  = (left_index + right_index) / 2;                 }                 if (strcmp(array[mid_index]->value, target) == 0)                         return (int) mid_index;         }                 return -1; }```
- I think the binary search algo also moves the right_index when appropriate.
- strcmp is expensive, can you remove any calls to strcmp?
- What happens if a negligent coder passes unsorted data to your function?
• 07-02-2004
dbtid
Quote:

Originally Posted by C+++C_forever
> midPtr = ( (leftPtr-kennel) + (rightPtr-kennel)) / 2 + kennel;

if i am not wrong, its because kennel is a pointer to a pinter. yoo should dereference the kernels..

Anyway, i actually post to ask my question on binary search. The complexity of it is logN ( = log base 10 N ) ok? But shouldn't it be log base 2 N ?

Yes, the complexity of a binary search is O(log2 (N)).
As an example, if you have 127 elements you want to search
through, you can guarantee a decision one way or another in
7 or less steps because log2(127) + 1 = 7.
• 07-02-2004
DavT
log2(N) = log10(N) / log10(2) = k*log10(N) where k is a constant.

so O(log2(N)) = O(log10(N)) = O(ln(N)) = ......

since constants are omitted in O() notation.

{the equals sign may not be the best representation to
use. I'm trying to say that they are equivalent I guess}
• 07-02-2004
Prelude
>- I think the binary search algo also moves the right_index when appropriate
The traditional algorithm for binary search modifies both the right_index and the left_index:
Code:

```low := 0 high := n - 1 while low <= high do   mid := (low + high) / 2   if x < array[mid] then     high := mid - 1   else if x > array[mid] then     low := mid + 1   else     return mid   endif loop return -1```
The same changes are made for a pointer based rather than index based implementation.

>- What happens if a negligent coder passes unsorted data to your function?
Checking to see if the data is already sorted can be expensive. This is a difficult tradeoff that most people usually make undefined and expect the client code to be smart enough to use it properly. :)
Show 80 post(s) from this thread on one page
Page 1 of 4 1234 Last