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

  1. #1
    Registered User
    Join Date
    Jun 2004
    Posts
    17

    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;
    	
    }
    Last edited by mgimbl; 07-01-2004 at 11:03 PM.

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

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

  4. #4
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    you are right that the pointers themselves are of StructTypes but when you do the arithmatic on them the result is an integer.

  5. #5
    Registered User
    Join Date
    Jun 2004
    Posts
    17
    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
    Last edited by mgimbl; 07-01-2004 at 11:03 PM.

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

  7. #7
    Registered User
    Join Date
    Jun 2004
    Posts
    17
    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;
    	
    }
    Last edited by mgimbl; 07-01-2004 at 11:53 PM.

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

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

  10. #10
    Yes, my avatar is stolen anonytmouse's Avatar
    Join Date
    Dec 2002
    Posts
    2,544
    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?
    Last edited by anonytmouse; 07-02-2004 at 04:36 AM.

  11. #11
    Registered User
    Join Date
    Jul 2004
    Posts
    6
    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.

  12. #12
    Registered User
    Join Date
    Mar 2003
    Posts
    143
    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}
    Last edited by DavT; 07-02-2004 at 07:28 AM.
    DavT
    -----------------------------------------------

  13. #13
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >- 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.
    My best code is written with the delete key.

  14. #14
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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
    Last edited by Thantos; 07-02-2004 at 08:43 AM.

  15. #15
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Right and there is never a time to use goto or continue or 3+ dimensional arrays.
    You forgot the smiley after that statement.
    My best code is written with the delete key.

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