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?
}
*/
//*****************************************************************************************

---

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

---

Binary search, directly from K&R2:

Quote:

---

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

> 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

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

}

//*****************************************************************************************

---

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

Quote:

---

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

Quote:

---

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.

:D

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

---

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.

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.

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.