Thread: Need help with binary search.

  1. #1
    Registered User
    Join Date
    Mar 2009
    Posts
    24

    Need help with binary search.

    I'm trying to create a binary search to go through my array. Never done this before, so I'm working mostly off of examples.

    Here's the code for my search function:

    Code:
    int binsearch(int A[], int top, int bot, int look)
    {
    int retval; 
    int mid;
    	
    	mid=(top + bot)/2;
    
    	if (top < bot)
    		retval =-1;
    	else if (look == A[mid])
    		retval=mid;
    	else if (look < A[mid])
    		retval=binsearch(A,bot,mid-1,look);
    	else
    		retval=binsearch(A,mid+1,top,look);
    
    	printf("%i", retval);
    
    return retval;
    }
    I have it displaying retval for my own purposes, just to see why it's not working. I get -1 returned each time.


    Here's my entire code:

    Definitions
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include "sort.h"
    
    /*=======================================================================================*/
    void sortArray(int A[] , int num)
    { 
    	int o;
    	int j;
    
    	for (o = 0; o < num-1; o++)
    	{ 
    		j = indexSmallest(A, o, num);
    		
    		if (j!= o)		
    			swap(&A[j], &A[o]);
    	}
    
    
    return;
    }
    
    /*=======================================================================================*/
    int indexSmallest(int A[] ,int o ,int n)
    { 
    int j;
    int ret = o;
    	
    	for (j = o + 1; j < n; j++)
    	
    	if (A[j] < A[ret])
    		ret = j;
    
    return ret;
    }
    
    /*=======================================================================================*/
    void swap(int *X,int *Y)
    { 
    int temp;
    
    	temp= *X;
    	
    	*X = *Y;
    	
    	*Y=temp;
    
    return;
    }
    /*=======================================================================================*/
    void printArray(int A[],int num)
    { 
    	int j;
    	for (j = 0; j < num; j++)
    	printf("A[%i] = %i\n", j, A[j]);
    
    return;
    }
    /*=======================================================================================*/
    int binsearch(int A[], int top, int bot, int look)
    {
    int retval; 
    int mid;
    	
    	mid=(top + bot)/2;
    
    	if (top < bot)
    		retval =-1;
    	else if (look == A[mid])
    		retval=mid;
    	else if (look < A[mid])
    		retval=binsearch(A,bot,mid-1,look);
    	else
    		retval=binsearch(A,mid+1,top,look);
    
    	printf("%i", retval);
    
    return retval;
    }
    Main function
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include "sort.h"
    
    #define N 100
    #define MAXVALUE 1000
    
    int look, k;
    int A[N];
    char temp;
    int n;
    int index;
    
    int main (void)
    
    { /*BEGIN MAIN*/
    	
    	srand(time(0)); /*Seed random number generator.*/
    	
    	for (k = 0; k < N; k++)
    	{
    		A[k]=(rand()%1000)+1; /*Fill the array.*/
    	}
    
    	sortArray(A,N); /*Call sortArray to sort the array.*/
    	printArray(A,N); /*Call printArray to print the array.*/
    	
    /*=================================================================================================*/	
    	printf("\nSearch for a number [1-1000] or [-1] to terminate:"); /*Ask for number to search.*/
    	scanf("%i", &look); /*Assign value to "look" variable.*/
    
    	while (look != -1)
    	{/*BEGIN SEARCH LOOP*/
    
    		if ((index=binsearch(A, 0, MAXVALUE-1, look))==-1)
    		{
    			printf("\nNo match found for: %i \n",look);
    		}
    		else
    		{
    			printf("\nValue: %i found at index %i\n", look, index);
    		}
    
    		printf("\nSearch for a number [1-1000] or [-1] to terminate:");
    		scanf("%i", &look);
    
    	}/*END SEARCH LOOP*/
    /*=================================================================================================*/
    
    return 0;
    } /*END MAIN*/
    Like I said, I'm working mostly off of examples here. Hopefully there's an obvious fix.
    Last edited by StateofMind; 05-06-2009 at 01:40 PM.

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Quote Originally Posted by StateofMind View Post
    I'm trying to create a binary search to go through my random array.
    A binary search such as you are attempting is nearly useless in a randomized array. The array needs to be sorted for a binary search to be useful.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Registered User
    Join Date
    Mar 2009
    Posts
    24
    Quote Originally Posted by hk_mp5kpdw View Post
    A binary search such as you are attempting is nearly useless in a randomized array. The array needs to be sorted for a binary search to be useful.
    It is sorted. Have a function for that too.

  4. #4
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Didn't see that. See what happens when you don't read the whole post. I just saw "random array" and "binary search" and I went "Bleargh, you can't do that!" I'll take a closer look.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  5. #5
    Registered User
    Join Date
    Mar 2009
    Posts
    24
    Quote Originally Posted by hk_mp5kpdw View Post
    Didn't see that. See what happens when you don't read the whole post. I just saw "random array" and "binary search" and I went "Bleargh, you can't do that!" I'll take a closer look.
    "Random array" is probably a bit misleading. Edited that out. I was just referring to the fact that it was generated randomly.

  6. #6
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    OK, two problems I see:

    Code:
    int binsearch(int A[], int top, int bot, int look)
    {
    int retval; 
    int mid;
    	
    	mid=(top + bot)/2;
    
    	if (top < bot)
    		retval =-1;
    	else if (look == A[mid])
    		retval=mid;
    	else if (look < A[mid])
    		retval=binsearch(A,bot,mid-1,look);
    	else
    		retval=binsearch(A,mid+1,top,look);
    
    	printf("%i", retval);
    
    return retval;
    }
    
    ...
    
    if ((index=binsearch(A, 0, MAXVALUE-1, look))==-1)
    {
       printf("\nNo match found for: %i \n",look);
    }
    The first problem is that your passing MAXVALUE-1 as the third argument to the binsearch function. MAXVALUE is the biggest integer you randomly create, not the biggest index (which is N) which is what you want to put there.

    The second problem is that in all your calls to the function, the lower index is passed as the second value and the bigger index is passed as the third. However, in the function, the arguments are top followed by bottom. These need to be switched around.

    This (I believe should work):

    Code:
    int binsearch(int A[], int bot, int top, int look)
    {
    int retval; 
    int mid;
    	
    	mid=(top + bot)/2;
    
    	if (top < bot)
    		retval =-1;
    	else if (look == A[mid])
    		retval=mid;
    	else if (look < A[mid])
    		retval=binsearch(A,bot,mid-1,look);
    	else
    		retval=binsearch(A,mid+1,top,look);
    
    	printf("%i", retval);
    
    return retval;
    }
    
    ...
    
    if ((index=binsearch(A, 0, N-1, look))==-1)
    {
       printf("\nNo match found for: %i \n",look);
    }
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  7. #7
    Registered User
    Join Date
    Mar 2009
    Posts
    24
    Quote Originally Posted by hk_mp5kpdw View Post
    fix
    Works perfectly. Thank you so much.

    I always manage to fall into little logic errors like N -> MAXVALUE. It's just hard to keep track of everything I guess. Thanks again!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  2. deleting all nodes of a binary search tree...
    By sachitha in forum C++ Programming
    Replies: 3
    Last Post: 09-29-2004, 06:19 AM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM