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

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

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

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.