Binary Searching a Structure Array

This is a discussion on Binary Searching a Structure Array within the C Programming forums, part of the General Programming Boards category; Gday All, I'm currently writing a program using structures to accept input from the user including student number, student name ...

  1. #1
    Registered User
    Join Date
    Aug 2002
    Posts
    34

    Binary Searching a Structure Array

    Gday All,

    I'm currently writing a program using structures to accept input from the user including student number, student name and phone number.
    THe program needs to accept this input, sort the arrays alphabetically and then print out the results to the user.
    This is all fine. Then the user needs to be able to search for a name, and the details are returned to the user. I have the alternative of linear search or binary search.

    Considering that the records will be sorted, i figure that binary search should be used as it is far more efficient.

    I have everything working fine, except for the binary search of which i have no idea about. There is no information in any text book i have, and any examples or tutorials involve linked lists and files etc. which i have not come across yet. (e.g. fopen, node )

    If anybody could lend a hand in helping me with a function to search the records i would be highly appreciative.

    Sorry that i cannot post any code of the binary search function, but i can't even get my head around it.

    Thanks.

    Code:
    #include <stdio.h> 
    #include <stdlib.h>
    #include <string.h>
    #define MAX_STUDENTS 10 
    
    typedef struct { 
    char studentNum[10];
    char lastName[ 15 ]; 
    char firstName[ 10 ]; 
    char phoneNum[ 15 ]; 
    } studentData; 
    
    void read_studentRecord( studentData [] ); 
    void print_studentRecord( studentData [] ); 
    void sort_studentRecord( studentData [] );
    //void search_studentRecord( studentData [] );
    
    //****************************************************************************************** 
    
    int main() 
    
    { 
    
    
    
    studentData details [MAX_STUDENTS]; //define a structure array of size MAX_STUDENTS 
    
    read_studentRecord( details );
    
    sort_studentRecord( details ); 
    
    print_studentRecord( details ); 
    
    //search_studentRecord( details );
    
    return 0; 
    
    } 
    
    //****************************************************************************************** 
    
    void read_studentRecord ( studentData details[] ) 
    { 
    int i = 0; 
    printf( "Enter Student Number (e.g. S00054321, 0 to end input)\n" ); 
    scanf( "%s", details[i].studentNum ); 
    while ( details[i].studentNum[0] != '0' ) 
    { 
    printf (" Enter Last Name:\n?"); 
    scanf ( "%s", details[i].lastName ); 
    
    printf (" Enter First Name:\n?"); 
    scanf ( "%s", details[i].firstName ); 
    
    printf (" Enter Phone Number:\n?"); 
    scanf ( "%s", &details[i].phoneNum ); 
    
    i++;
     
    printf ( "Enter Student Number\n?"); 
    scanf ( "%s", details[i].studentNum); 
    
    
    } 
    } 
    
    //*****************************************************************************************
    
    void sort_studentRecord ( studentData details[] )
    {
    
    studentData hold;
    int i, pass;
    
    
    for ( pass = 1; pass <= 3 - 1; pass++ )//number of passes
    
          for ( i = 0; i <= 3 - pass -1; i++ )//single pass      
    
    		  if ( strcmp( details[i].lastName, details[i+1].lastName ) == 1) {//sort in order of last name
    
    		     hold = details[i];
                 details[i] = details[i+1];//swap array elements if statement is true
    			 details[i+1] = hold;
    
              }
    }
    
    
    //***************************************************************************************** 
    
    void print_studentRecord( studentData details[] ) 
    { 
    int i=0; 
    if (details[0].studentNum != 0) 
    printf ("\n%-10s%-16s%-11s%10s\n\n", "Student #", "Last Name", "First Name", "Phone #"); 
    
    while ( details[i].studentNum[0] != '0' ) 
    { 
    printf("%-10s%-16s%-11s%10s\n", details[i].studentNum, details[i].lastName, details[i].firstName, details[i].phoneNum); 
    
    i++; 
    } 
    
    } 
    
    //*****************************************************************************************
    /*
    void search_studentRecord( studentData details[] )
    {
    	I dont think this will have a void return value?
    }
    */
    //*****************************************************************************************

  2. #2
    Registered User mlupo's Avatar
    Join Date
    Oct 2001
    Posts
    72
    Not sure if this will help but here's a example 10.10 from the book 'Programming in C' by steven G. Kochan.
    Code:
    // a dictionary to look up words and return an definition.
    
    //preprocessor statements
    #include<stdio.h>
    
    //define structure
    struct entry
    {
    	char word[10];
    	char definition[50];
    };
    
    //test to see if strings are equal
    int compare_strings(char s1[], char s2[])
    {
    	int i =0, answer;
    
    	while (s1[i] == s2[i] && 
    		   s1[i] != '\0' && s2[i] != '\0')
    		++i;
    	
    	if ( s1[i] < s2[i] )
    		answer = -1; // s1 < s2
    	else if ( s1[i] == s2[i] )
    		answer = 0; //strings are equal
    	else
    		answer = 1; //s1 > s2
    
    	return (answer);
    }
    
    //function to look up words in a dictionary
    int lookup(struct entry dictionary[], char search[],
    		   int entries)
    {
    	int mid, result;
    	int high = entries - 1;
    	int low = 0;
    	int compare_strings(char s1[], char s2[]);
    
    	while ( low <= high )
    	{
    		mid = (low + high) / 2;
    		result = compare_strings(dictionary[mid].word, search);
    
    		if (result == -1)
    			low = mid + 1;
    		else if (result == 1)
    			high = mid - 1;
    		else
    			return mid;
    	}		
    	return -1;	
    }
    
    main()
    {
    	struct entry dictionary[100] = 
    	{	
    	{"aardvark","a burrowing african animal"		},
    	{"abyss",	"a bottomless pit"					},
    	{"acumen",	"mentally sharp, keen"				},
    	{"addle",	"to become confused"				},
    	{"aerie",	"a high nest"						},
    	{"affix",	"to append; attach"					},
    	{"agar",	"a jelly made from seaweed"			},
    	{"ahoy",	"a nautical call of greeting"		},
    	{"aigrette","an ornamental cluster of feathers"	},
    	{"ajar",	"a US Marine's haircut"				},
    	};
    
    	char word[10];
    	int entries = 10;
    	int entry_number;
    	int lookup(struct entry dictionary[], char search[],
    		int entries);
    
    	printf("Enter word: ");
    	scanf("%9s", word);
    	entry_number = lookup (dictionary, word, entries);
    
    	if (entry_number != -1)
    		printf("\n%s\n\n\n", dictionary[entry_number].definition);
    	else
    		printf("Sorry, that words is not in my dictionary\n\n");
    }
    NEVER PET YOUR DOG WHILE IT'S ON FIRE!

  3. #3
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Binary search, directly from K&R2:
    Binary search first compares the input value x to the middle element of the array v. If x is less than the middle value, searching focuses on the lower half of the table, otherwise on the upper half. In either case, the next step is to compare x to the middle element of the selected half. This process of dividing the range in two continues until the value is found or the range is empty.
    Code:
    /* binsearch:  find x in v[0] <= v[1] <= ... <= v[n-1] */
       int binsearch(int x, int v[], int n)
       {
           int low, high, mid;
    
           low = 0;
           high = n - 1;
           while (low <= high) {
               mid = (low+high)/2;
               if (x < v[mid])
                   high = mid + 1;
               else if (x  > v[mid])
                   low = mid + 1;
               else    /* found match */
                   return mid;
           }
           return -1;   /* no match */
       }
    This is an example for searching an int array, but you can adapt it to do whatever you want. If you want to cheat, lookup bsearch().
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,765
    > void read_studentRecord ( studentData details[] )
    I think it would be better if this returned the number of student details read in, for use inside the sort / print / search functions

    Code:
    int read_studentRecord ( studentData details[] ) {
      // your code
      return i;
    }
    Then you can do
    Code:
    num = read_studentRecord( details );
    sort_studentRecord( details, num ); 
    print_studentRecord( details, num );
    > strcmp( details[i].lastName, details[i+1].lastName ) == 1
    This isn't what strcmp normally returns

    strcmp(a,b) returns < 0 if a is before b
    strcmp(a,b) returns == 0 if a is the same as b
    strcmp(a,b) returns > 0 if a is after b

    You typically want
    strcmp( details[i].lastName, details[i+1].lastName ) < 0
    to implement a sort function
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Aug 2002
    Posts
    34
    I have tried to append a sorting function to my program, but it is just not happening for me. It's given me 3 main warnings to do with differing in levels of indirection . I think it is because i am using the structure type as the data type in the function or something.

    If anyone could just have a look to see what i am doing wrong here, because i can't really see the problem.

    Thanks

    here is the updated code:

    Code:
    #include <stdio.h> 
    #include <stdlib.h>
    #include <string.h>
    #define MAX_STUDENTS 10 
    
    typedef struct { 
    char studentNum[10];
    char lastName[ 15 ]; 
    char firstName[ 10 ]; 
    char phoneNum[ 15 ]; 
    } studentData; 
    
    void read_studentRecord( studentData [] ); 
    void print_studentRecord( studentData [] ); 
    void sort_studentRecord( studentData [] );
    void search_studentRecord( studentData [] );
    
    //****************************************************************************************** 
    
    int main() 
    
    { 
    
    
    
    studentData details [MAX_STUDENTS]; //define a structure array of size MAX_STUDENTS 
    
    read_studentRecord( details );
    
    sort_studentRecord( details ); 
    
    print_studentRecord( details ); 
    
    search_studentRecord( details );
    
    return 0; 
    
    } 
    
    //****************************************************************************************** 
    
    void read_studentRecord ( studentData details[] ) 
    { 
    int i = 0; 
    printf( "Enter Student Number (e.g. S00054321, 0 to end input)\n" ); 
    scanf( "%s", details[i].studentNum ); 
    while ( details[i].studentNum[0] != '0' ) 
    { 
    printf (" Enter Last Name:\n?"); 
    scanf ( "%s", details[i].lastName ); 
    
    printf (" Enter First Name:\n?"); 
    scanf ( "%s", details[i].firstName ); 
    
    printf (" Enter Phone Number:\n?"); 
    scanf ( "%s", &details[i].phoneNum ); 
    
    i++;
     
    printf ( "Enter Student Number\n?"); 
    scanf ( "%s", details[i].studentNum); 
    
    
    } 
    } 
    
    //*****************************************************************************************
    
    void sort_studentRecord ( studentData details[] )
    {
    
    studentData hold;
    int i, pass;
    
    
    for ( pass = 1; pass <= 3 - 1; pass++ )//number of passes
    
          for ( i = 0; i <= 3 - pass -1; i++ )//single pass      
    
    		  if ( strcmp( details[i].lastName, details[i+1].lastName ) == 1) {//sort in order of last name
    
    		     hold = details[i];
                 details[i] = details[i+1];//swap array elements if statement is true
    			 details[i+1] = hold;
    
              }
    }
    
    
    //***************************************************************************************** 
    
    void print_studentRecord( studentData details[] ) 
    { 
    int i=0; 
    if (details[0].studentNum != 0) 
    printf ("\n%-10s%-16s%-11s%10s\n\n", "Student #", "Last Name", "First Name", "Phone #"); 
    
    while ( details[i].studentNum[0] != '0' ) 
    { 
    printf("%-10s%-16s%-11s%10s\n", details[i].studentNum, details[i].lastName, details[i].firstName, details[i].phoneNum); 
    
    i++; 
    } 
    
    } 
    
    //*****************************************************************************************
    void search_studentRecord( studentData details[] )
    {
    	int low, high, mid, searchkey;
    
    	printf("Enter a student number to search for e.g. s00012345\n");
    	scanf("%s", &searchkey);
    
           low = 0;
           high = MAX_STUDENTS - 1;
           while (low <= high) {
               mid = (low+high)/2;
               if (searchkey < details[mid].studentNum)
                   high = mid + 1;
               else if (searchkey  > details[mid].studentNum)
                   low = mid + 1;
               else if (searchkey == details[mid].studentNum)    /* found match */
                  printf("Name: %s %s\nPhone Number: %s\n", details[mid].firstName, details[mid].lastName, details[mid].phoneNum);
    		   else
    			   printf("Search Key not found\n");
           }
            
       
    
    }
    
    //*****************************************************************************************

  6. #6
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    >>>If anyone could just have a look to see what i am doing wrong here, because i can't really see the problem.
    Read Salem's post re the use of strcmp().
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  7. #7
    Registered User mlupo's Avatar
    Join Date
    Oct 2001
    Posts
    72
    Originally posted by Simon
    >>>typedef struct {
    char studentNum[10];
    char lastName[ 15 ];
    char firstName[ 10 ];
    char phoneNum[ 15 ];
    } studentData;

    Is there any reason in particular that StudentNum is declared to be of type char rather than type int?

    See, in your functions below, you are doing integer type comparisons....

    if (searchkey < details[mid].studentNum)
    What you're asking your program to do here is to compare something like
    16<apples. Can't do that on a calculator can ya?
    :-)

    so either change the type of StudentNum to int
    or...
    use strcmp to verify if two strings are equal.
    strcmp() returns 0 if str1 = str2 or
    greater than 0 if str1 is > than str2 or
    less than 0. if str1 < than str2.

    NEVER PET YOUR DOG WHILE IT'S ON FIRE!

  8. #8
    Registered User
    Join Date
    Aug 2002
    Posts
    34
    I seem to have got near the problem,
    but i cannot figure out why the search wont recognise that the searchkey has been input. i.e if i put the student number: s00027369, and search for it, "Not found",

    Anybody have any suggestions on what i should do?
    Here is the code:

    Code:
    #include <stdio.h> 
    #include <stdlib.h> 
    #include <string.h> 
    #define MAX_STUDENTS 3 
    
    typedef struct { 
    char studentNum[10]; 
    char lastName[ 15 ]; 
    char firstName[ 10 ]; 
    char phoneNum[ 15 ]; 
    } studentData; 
    
    int read_studentRecord( studentData [] ); 
    void print_studentRecord( studentData [] ); 
    void sort_studentRecord( studentData [] ); 
    void search_studentRecord( studentData [], int ); 
    
    // ************************************************** 
    //**************************************** 
    
    int main() 
    
    { 
    int n; 
    
    studentData details [MAX_STUDENTS]; //define a structure array of size MAX_STUDENTS 
    
    n = read_studentRecord( details ); 
    
    sort_studentRecord( details ); 
    
    print_studentRecord( details ); 
    
    search_studentRecord( details, n ); 
    
    return 0; 
    } 
    
    // ************************************************** 
    //**************************************** 
    
    int read_studentRecord ( studentData details[] ) 
    { 
    int i = 0; 
    printf( "Enter Student Number (e.g. S00054321, 0 to end input)\n" ); 
    scanf( "%s", details[i].studentNum ); 
    while ( details[i].studentNum[0] != '0' ) 
    { 
    printf (" Enter Last Name:\n?"); 
    scanf ( "%s", details[i].lastName ); 
    
    printf (" Enter First Name:\n?"); 
    scanf ( "%s", details[i].firstName ); 
    
    printf (" Enter Phone Number:\n?"); 
    scanf ( "%s", &details[i].phoneNum ); 
    
    i++; 
    
    printf ( "Enter Student Number\n?"); 
    scanf ( "%s", details[i].studentNum); 
    } 
    return i; 
    } 
    
    // ************************************************** 
    //*************************************** 
    
    void sort_studentRecord ( studentData details[] ) 
    { 
    
    studentData hold; 
    int i, pass; 
    
    for ( pass = 1; pass <= 3 - 1; pass++ )//number of passes 
    for ( i = 0; i <= 3 - pass -1; i++ )//single pass 
    if ( strcmp( details[i].lastName, details[i+1].lastName ) == 1) {//sort in order of last name 
    hold = details[i]; 
    details[i] = details[i+1];//swap array elements if statement is true 
    details[i+1] = hold; 
    } 
    } 
    
    
    // ************************************************** 
    //*************************************** 
    
    
    void print_studentRecord( studentData details[] ) 
    { 
    int i=0; 
    if (details[0].studentNum != 0) 
    printf ("\n%-10s%-16s%-11s%10s\n\n", "Student #", "Last Name", "First Name", "Phone #"); 
    
    while ( details[i].studentNum[0] != '0' ) 
    { 
    printf("%-10s%-16s%-11s%10s\n", details[i].studentNum, details[i].lastName, details[i].firstName, details[i].phoneNum); 
    
    i++; 
    } 
    } 
    
    // ************************************************** 
    //*************************************** 
    
    //PROBLEMS!!! 
    
    void search_studentRecord( studentData details[], int numOfRec ) 
    { 
    int low, high, mid; 
    char searchkey[10]; 
    int flag = 0; 
    printf("Enter a student number to search for e.g. s00012345\n"); 
    scanf("%s", searchkey); 
    
    low = 0; 
    high = numOfRec; 
    
    while (low <= high) { 
    mid = (low+high)/2; 
    if (strcmp(searchkey, details[mid].studentNum) < 0) 
    high = mid-1; 
    else if (strcmp(searchkey, details[mid].studentNum) > 0) 
    low = mid + 1; 
    else if (strcmp(searchkey, details[mid].studentNum) == 0) /* found match */ 
    { 
    printf("Name: %s %s\nPhone Number: %s\n", details[mid].firstName, details[mid].lastName, details[mid].phoneNum); 
    flag = 1; 
    break; 
    } 
    } 
    
    if (!flag) printf("Search Key not found\n"); 
    }

  9. #9
    Registered User
    Join Date
    Aug 2002
    Posts
    34
    Sorry about double posting,

    but the results vary, it seems that it will return details about the student but only if a certain number of entries have been put in, or if the student number is a certain amount of characters long.

    I can't figure out what the problem is becuse the results are not consistent at all.

  10. #10
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,765
    For a binary search to work, the array has to be sorted with the SAME key that is used for searching

    So in order to be able to binary search using studentNum as the key field, you've got to sort the array using studentNum

    Presently, your sort is
    a) broken
    See previous posts on use of strcmp
    > strcmp( details[i].lastName, details[i+1].lastName ) == 1
    is wrong

    b) short
    > for ( pass = 1; pass <= 3 - 1; pass++
    Try passing the number of records to this function, as previously suggested

    c) it's the wrong key
    You're trying to sort by lastName, not studentNum

    You have this in main
    sort_studentRecord( details );
    print_studentRecord( details );
    search_studentRecord( details, n );

    Which I suggest you turn into
    sort_studentRecord( details, n );
    print_studentRecord( details, n );
    search_studentRecord( details, n );

    Until print is showing the correct answers, the best thing you can do with search is delete it (or save it elsewhere for later), because you're going nowhere until sort is working properly.



    If you're in the position of having to sort by lastName, but search for studentNum, then a binary search is not the answer.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  11. #11
    Registered User
    Join Date
    Aug 2002
    Posts
    34
    Salem,

    I understand what you have done now, so i will change the searching to be by last name, as it is a requirement.

    Thanks for your help, appreciate it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 7
    Last Post: 11-25-2008, 01:50 AM
  2. Dynamic structure with array and array count
    By Nazgulled in forum C Programming
    Replies: 14
    Last Post: 06-08-2007, 11:10 PM
  3. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 05:15 AM
  4. Replies: 41
    Last Post: 07-04-2004, 04:23 PM
  5. Structure Array searching
    By ling in forum C Programming
    Replies: 4
    Last Post: 10-18-2001, 01:39 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21