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;
	
}

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;

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?

you are right that the pointers themselves are of StructTypes but when you do the arithmatic on them the result is an integer.

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

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;

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;
	
}

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;

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 ...

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;
}

Things to think about:
- 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?

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.

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}

>- 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.

There is one golden rule with pointer arithmetic - "Don't use pointer arithmetic!".

Right and there is never a time to use goto or continue or 3+ dimensional arrays.

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

Good catch, its amazing what I can miss when I am haven't had enough sleep

>Right and there is never a time to use goto or continue or 3+ dimensional arrays.
You forgot the smiley after that statement.