Binary Search

[emmas4impact]

hello everyone,
I wrote some code on binary search in algorithms using c but here is my problem:

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <ctype.h>

/*


TASK: Demo about static, linear data handling.
   Four basic operations are exercised:
   1) find
   2) insert
   3) modify
   4) delete

   5) show
   6) quit
   7) ? meaning help


 
QUESTIONS, :
   Task of this year. Do firstly following:

   
  
   1) Modifying is still missing. Program it now. Also find by name and ask how the ID shoudl
      be changed!
   2)later....
   3) Add the third column in the students' description, the gender. It can be described as
      char cGender[M] which can have values '? ' or '? ' for women and men or 1 and 0.
   4) Change the full program to work with studend IDs, not with the names!
   5) Add a new function (command like (r)everse) to sort the data in reverse order and
   warn that after that it would no more work without sorting it back. After that show, sort it
   back into ascending order.
   6) Add a new filed into the program. It tells the students' age in years. Also int iYears[N];
   It must become visible when showing or storing/retreaving the lists.
   7) Disable same student ID's in the generation phase.




----------------------------------------------------------------------------------
*/

//GLOBAL CONSTANT
#define M 40 //max items
#define CMDS 7 //how many commands programmed

//PROTOTYPES
int GetAnsw( char []);
int ShuttleSortN(int [], char [][16], int);
int ShowTable(int [], char [][16], int);
int ShowCommands(char [][10], int);
int FindSequentially(char [], char [][16], int , int *);
int DoBinarySearch(char [], char [][16], int, int *);

int main()
{
   int N= M - 10;  //the rest 10 % of the table area is in reserve for insertions
   int i, j;

   time_t  Start1, Finish1;
   double  dDuration1;

   FILE *InputChannel;
   FILE *OutputChannel;
   char OutputFile[]= "C:/users/students.DAT";
   char InputFile[]= "C:/users/students.DAT";
   int InputSuccessful= 1; 
   int OutputSuccessful= 1;

	char cFirstName[28][16]={
	   {"Adewale"},
	   {"Oluyemi"},
	   {"Emma"},
	   {"Okoyomo"},
	   {"Seyi"},
	   {"Rita"},
	   {"Lekan"},
	   {"Sandra"},
   	   {"John"},
	   {"Kenny"},
	   {"Elijah"},
	   {"Olumide"},
	   {"oribogunje"},
	   {"Funsho"},
	   {"Temilehin"},
	   {"Olu-Osho"},
	   {"asha"},
	   {"Bimbo"},
	   {"Ade"},
	   {"Adeokin"},
	   {"Adeojo"},
	   {"Agboola"},
	   {"Iyabo"},
	   {"Yinka"},
	   {"Dayo"},
	   {"Toyin"},
	   {"Wande"},
	   {"Bimpe"}
   };
   char czCommand[80];
   char czCmdHelp[CMDS][10]={
      "(D)el",
	  "(F)ind",
	  "(I)ns",
	  "(M)od",
	  "(S)how",
	  "(Q)uit",
	  "? help"
   };
    char czCmds[CMDS][10]={
      "Del",
	  "Find",
	  "Ins",
	  "Mod",
	  "Show",
	  "Quit",
	  "?"
   };
   char name[20], answ[20];
   int iStudID[M];
   char czStudentName[M][16];
   int iNameL;
   int iFound;
   int iRetCode= 0;

   //Is there anything in the input file
   printf ("\nGive input file name if any (=CR): ");
   GetAnsw(InputFile);
   if (strcmp(InputFile, "")== 0)
	  InputChannel= NULL;
   else{
      InputChannel= fopen(InputFile,"tr");
   }
   if (InputChannel == NULL){
      printf ("\nInput %s substituted by randomly generated records!", InputFile);
      //fill the vectors with arbitrary values for names and ID-codes
      for(i= 0; i< N; i++){
		 iStudID[i]= rand() % (N*100) + 10000; //for N= 10, rand. values => 10000.. 19999
		 //first name plus a acharacter for surname
		 strcpy(czStudentName[i], cFirstName[rand()% 28]);
		 iNameL= strlen(czStudentName[i]);
		 czStudentName[i][iNameL]= ' ';
		 czStudentName[i][iNameL + 1]= rand() % 24 + 'A';
		 czStudentName[i][iNameL + 2]= '.';
		 czStudentName[i][iNameL + 3]= 0;  //the binary ending
	  }
   }
   else //reading the data from the input file without generating it
   { 
	   printf ("\nInput records will be taken from the file: %s!", InputFile);
	   i= 0;
   	   iRetCode= fscanf(InputChannel, "%d %s", &iFound, name);
	   printf("\n%d. record: %d %s", i, iFound, name);
	   while ((iRetCode != EOF) && (i < N)){
		  iStudID[i]= iFound;
		  strcpy(czStudentName[i], name);
		  i++;
          iRetCode= fscanf(InputChannel, "%d %s", &iFound, name);
		  printf("\n%d. record: %d %s", i, iFound, name);
	   }
	   N= i; 
       printf("\nRed %d. records!", N);
       fclose(InputChannel);
    }


	//original data:
	printf("\nTEST: Unsorted data:\n");
    ShowTable(iStudID, czStudentName, N);

	//Sort algorihtms used for >= 4 items:
	printf("\n\nTEST: Sorted in ascending order according to name:\n");
	iRetCode= ShuttleSortN(iStudID, czStudentName, N);
    ShowTable(iStudID, czStudentName, N);
 
	//Eternal loop to handle all operations:
	while (1){
	    printf("\nGive command: ");	
	    GetAnsw(czCommand);
	    //we also homogenize lowercases and uppercases 
	    czCommand[0]= toupper(czCommand[0]);
	    //printf("\nTEST: Your command was: %s", czCommand);


	    if (strcmp(czCmds[0],czCommand)==0 ||
		   czCmds[0][0]==czCommand[0]){ //del
		   printf("\nDeleting: which name? ");
		   GetAnsw(name);
		   //It would be more "elegant" if this deletion would also use
		   //the newest FindSequentially-subroutine...
		   for (i=0; i< N; i++){
   			   //printf("\nTEST: Comparing %s <> %s", name, cFirstName[i]);
			   if (strcmp(name, czStudentName[i])==0){
			   //lift the rest of the table higher to overlap the deleted
				   for (j= i; j<N-1; j++){
				      strcpy(czStudentName[j],czStudentName[j+1]);
					  iStudID[j]= iStudID[j+1];
				   };
				   N= N-1;
                   printf("\n%s deleted! Only %d records left!", name, N);
				   //ShowTable(iStudID, czStudentName, N);
				   break;
			   }
			   else if (i== N- 1) //at the end
                  printf("\nCould not delete an inexistent record!");
		   }
		}
		 
	    else if (strcmp(czCmds[1],czCommand)==0 || czCmds[1][0]==czCommand[0]) {
		//find
		   printf("\nFinding: Give the name to find: ");
		   GetAnsw(name);
		   printf("\nDo you perform (s)equential or (b)inary search? ");
		   GetAnsw(answ);
		   answ[0]= toupper(answ[0]);
		   if (answ[0]=='B') //also binary search
			  DoBinarySearch(name, czStudentName, N, &iFound);
		   else
 	          FindSequentially(name, czStudentName, N, &iFound);
		   if (iFound >= 0)
			  printf("\nFound %s with ID: %5d\n", 
			      czStudentName[iFound], iStudID[iFound]);
		   else
		      printf("\nNot found!\n");
		}
	    else if (strcmp(czCmds[2],czCommand)==0 ||
		   czCmds[2][0]==czCommand[0]) //insert
		{		
	       //printf("\nNot ready to insert...");
		   printf("\nInserting: Give the name: ");
		   GetAnsw(name);
		   //printf("... repeated: %s ", name);
		   FindSequentially(name, czStudentName, N, &iFound);
		   //printf("\nreturn code from finding: %d", iFound);
		   if (iFound > 0){ //old one exists, no insert
			  printf("\nAlready existing %s with ID: %5d\n", 
			      czStudentName[iFound], iStudID[iFound]);
		   }
		   else if (iFound == -9999)
			//no found,  the proper place for it is at the end
		   {
			//.... do your work here
		      strcpy(czStudentName[N], name);   
			  printf("\nGive the ID: ");
		      GetAnsw(name);
			  iStudID[N]= atoi(name);	
			  N= N +1;
			  printf ("\nInserted! There are now %d records!", N);
		   }
		   else if (iFound <= 0)
			//no found, the next place is iFound
		   {
		   //move the ending part of the table forward
			   iFound= abs(iFound);
			   //printf("\n...start insertion from this old name on: %d %s...", iFound, 				   czStudentName[iFound]);
			   for (i= N-1; i>= iFound; i--){
				   //printf("\nTest: should move: %d %s lower",iStudID[i],czStudentName[i]);
			      strcpy(czStudentName[i+1],czStudentName[i]); 
				  iStudID[i+1]= iStudID[i];
			   }
		       //insert the new item
		       strcpy(czStudentName[iFound],name);
			   printf("\nGive the ID: ");
		       GetAnsw(name);
			   iStudID[iFound]= atoi(name);	
			   N= N + 1;
		   }
		}
	    else if (strcmp(czCmds[3],czCommand)==0 ||
		   czCmds[3][0]==czCommand[0]) //modify
		{
	       printf("\nNot ready to modify...");
		}
	    else if (strcmp(czCmds[4],czCommand)==0 ||
		   czCmds[4][0]==czCommand[0]) //show
		{
		   printf("\nData set look like following:.\n");
		   ShowTable(iStudID, czStudentName, N);
		}
	    else if (strcmp(czCmds[5],czCommand)==0 ||
           czCmds[5][0]==czCommand[0]) {//quit
		   break;
	    }
		else if (strcmp(czCmds[6],czCommand)==0 ||
           czCmds[6][0]==czCommand[0]) //help
		{
   	       ShowCommands(czCmdHelp, CMDS);
	    }
	
		else  //error in command, help
		{
		   printf("\nData set look like following:.\n");
		   ShowTable(iStudID, czStudentName, N);
		   printf("\nError in command.\n");
	       ShowCommands(czCmdHelp, CMDS);
		}
	}
	
	//SAVING THE DATA INTO AN OUPUT FILE
   OutputChannel= fopen(OutputFile,"w");
   if (OutputChannel == NULL){
	   printf ("\nOutput file %s could not be opened (check the disk!)", OutputFile);
   }
    else{
       printf ("\nSaving into the output file %s\n", OutputFile);
	   for(i=0; i< N; i++){
	      iRetCode= fprintf(OutputChannel,"%d %s\n", iStudID[i], czStudentName[i]);
		  if (iRetCode==0)
		  {
		      printf("\nOutput problem. Check the disk space ...!");
			  break;
		  }
	   }
       fclose(OutputChannel);
	}
	
    //READY:
	printf("\nPush any key to end ...");
	getchar();
	return 0;
}

//SUBROUTINES ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
int GetAnsw( char Answ[]){
/*TASK: scanf subsituted by characterwise input 
FOR characters keyed
    IF CR
	   end the output string
    ELSE
	   insert the character into the input string
    END
END
---------------------------------------------------------------
*/
char cCh;
int i;
i= 0;
while (1){
   cCh= getchar();
   if (cCh== 13 || cCh== 10) {//CR or LF
	  Answ[i]= 0; //binary ending
	  break;
   }
   else{
	  Answ[i]= cCh;
      i++;
   }
}
return 0;
}

int ShowCommands(char czCmdHelp[][10], int N){
/*PSEUDOCODE: 
  FOR all commands
     show in the display
  END
  ---------------------------------------------------
*/
int i;
printf("\nUse  following commands (or one letter shortenings):\n");
for (i=0; i< CMDS; i++)
	printf("\n%s", czCmdHelp[i]);
return 0;
}

int ShuttleSortN (int myVect[], char cNames[][16], int iNumb){
//This is a record sorting, also not only a key sort!
/*PSEUDOCODE:
For right hand r: 0 .. N-2
    For left hand l: r  + 1 … N-1
        If  l’th value < r’th value
            Chance them (means swapping…)
            TempPlace= left value
            Left value = right value
            Right value= TempPlace 
        End
   End
End
*/

int r, l;
int k;
int swapInt;
char cTempName[16];

//l refers to left hand, r to right hand
for (r= 0;r <= iNumb-2; r++){
	for(l= r+1; l <= iNumb-1; l++){
	   //if (myVect[r] < myVect[l]){ //ascending sorting order
	   	if (strcmp(cNames[r],cNames[l])> 0){ //ascending sorting order
		//printf("\nTest: changed %s %s", cNames[r],cNames[l]);
	    // swap the key values:
		  swapInt= myVect[l];
          myVect[l]= myVect[r];
		  myVect[r]= swapInt;
		  //change also the other fields of the record
	      strcpy(cTempName, cNames[l]);
	      strcpy(cNames[l], cNames[r]);
          strcpy(cNames[r], cTempName);

	   }
	}
}
return 0;
}

 
int ShowTable(int iStudID[], char czStudentName[][16], int iNumb) {
/*
AUTHOR: T. Kallinen              DATE: 2008-4-2
PSEUDOCODE:
   IF items in the table
      FOR all items
	      display
   ELSE
      display: no items
   END
-----------------------------------------------------------------------------------------------
*/

int i;
printf("\nID   Name:\n");
if (iNumb== 0) 
   printf("\nThe table is empty!");
else {
   for(i= 0; i< iNumb; i++){
      printf("%5d %-13s", iStudID[i], czStudentName[i]);
      if (i % 4 == 3) 
         printf("\n");
   }
}
return 0;
}
///////////////////////////////////////////////////////////////////////////////
/*‘BINARY SEARCH ALGORITHM DESCRIPTION:
‘
‘                0.    1.   2.    3.    4.     5.   6.    7.   8.    9.    10.  11.                            
‘              +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+->all pointers
‘ Vector:      |17 | 18| 22| 22| 24| 25| 27| 31| 33| 36| 37| 41| 43| 46| 47| 51| 55|  
‘    of        +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
‘ N=12 items     ^                            ^                                  ^ 
‘                |                            |                                  |
‘             LowerBound                    MiddlePoint                    UpperBound
‘                |
‘             FoundPointer
‘
‘PSEUDOCODE:
‘ BinarySearch(Vector, SearchValue, FoundPointer, N)
‘FoundPointer= -1
‘LowerBound=0
‘UpperBound= N-1
‘DO WHILE UpperBound >= LowerBound AND FoundPointer = -1
‘       MiddlePoint= INT((LowerBound + UpperBound)/2)
‘       IF SearchValue < Vector(MiddlePointer) ‘   … we’ll search from the left half
‘            UpperBound= MiddlePoint – 1  ‘…rejecting the right half
‘       ELSE …we’ll search from the right half
‘            IF SearchValue = Vector(MiddlePoint) ‘we did find it now!
‘                 FoundPointer=  MiddlePoint 
‘            ELSE ‘reject the left part to move on to the right…
‘                 LowerBound= MiddlePoint + 1
‘            END IF
‘       END IF
‘END DO
‘COMMENT: Also found or not?
‘IF FoundPointer= -1
 ‘    Not found…
‘ELSE
‘    Found successfully
`    FoundPointer tells/returns the position
‘END IF
*/
int DoBinarySearch(char name[], char czStudentName[][16], int N, int *FoundPointer)
{

int Middlepoint,i=0;
int LowerB= 0;
int UpperB= N-1;
*FoundPointer= -1;
//here you shall fullfill the code
//printf ("\nBinary search not ready! Complete it\n");
while (UpperB > LowerB && *FoundPointer == -1)
{
	Middlepoint=(LowerB + UpperB)/2;
	if(strcmp(name, czStudentName[i])<0)
		*FoundPointer=Middlepoint-1;
	else{
		if(strcmp(name, czStudentName[i])==0)
			*FoundPointer=Middlepoint;
		else
			LowerB=Middlepoint + 1;
	}

   break;
}//COMMENT: Also found or not?
if(*FoundPointer= -1)
   printf("Not Found\n");
else
   printf("Found successfully!");

return *FoundPointer;
}

int FindSequentially(char name[], char czStudentName[][16], int iN, int *iFound){
int i;
for (i=0; i< iN; i++){
   //printf("\ncomparing %s and %s\n", name, czStudentName[i]);
   if (strcmp(name, czStudentName[i])==0){
	  //printf("\n%s has ID: %5d\n", czStudentName[i], iStudID[i]);
	  *iFound= i;
	  break;
   }
   else if (i== iN - 1) {//at the end
      //printf("\nCould not find an inexistent record!");
      *iFound= -9999;
	  break;
   }
   else if (strcmp(name, czStudentName[i])<0)
   {  
	  //printf("\nA bigger Key was found in the ascending order: %d %s", i,czStudentName[i]);
      *iFound= - i;
	  break;
   }
}
return 0;
}

my task is to write a code that modify the student name and that can search for name using binary search.

i will appreciate quick reply
Thanks

[BestJewSinceJC]

I hope you don't expect anyone to do your homework for you.

[WaltP]

That's a good task. If you need help, let us know what you need help with and we can help.

[Adak]

Suggestions for your Binary search function:

#
int DoBinarySearch(char name[], char czStudentName[][16], int N, int *FoundPointer)
{
int Middlepoint,i=0;
int LowerB= 0;
int UpperB= N-1;
You don't want a pointer set to -1. You want the index of the student, in the array, if found. Middlepoint already gives you that.
//here you shall fullfill the code
//printf ("\nBinary search not ready! Complete it\n");
while (UpperB >= LowerB)
{
    Middlepoint=(LowerB + UpperB)/2;
    /* just make ONE strcmp() and assign it to a variable. then make
        all your comparisons, to that variable
    */
     int result = strcmp() ...
     if(result <0)
      Upperb=Middlepoint-1;
     else if(result==0) 
            return Middlepoint;
     else
         LowerB=Middlepoint + 1;
}//COMMENT: Also found or not?
 return -1; //not found

Your function returns the results, let your calling function print any found/not found, messages.

I haven't run this binary search function, but the idea is what I'm trying to convey. You need no pointers, at all, since what you want is an index (integer). Middlepoint is that number, if the target value is found. You make just one strcmp() per loop, and use the result it returns to you, to make your logic for the search, work.

You can have this function print up the results, but if you do, watch out. Generally, you get the best looking output if the calling function (the higher function), handles all messages like that.

[emmas4impact]

Thanks i appreciate that idea a lot i will try it and get back to you

[emmas4impact]

After trying that code the result is still not found
below is what i did:-

while (UpperB >= LowerB)
{
    Middlepoint=(LowerB + UpperB)/2;
    int result=strcmp(name, czStudentName[i]);
    if (result <0)
        UpperB=Middlepoint-1;
    else if(result==0)
        return Middlepoint;
    else
        LowerB=Middlepoint + 1;


   break;
}//COMMENT: Also found or not?


return -1;
}

[Adak]

Let me put some example together. Back in a bit.

Please use code tags (the [code] icon in the edit or reply window), around your program.

Just highlight the code, and click on the [code] icon - then your program will look like a program, instead of being all squashed to the left margin of the window.

[Adak]

#include <stdio.h>
#include <string.h>

#define N 25

int DoBinarySearch(char name[], char SName[][N], int rows);

int main() {
  int i, rows = 7; 
  char name[N] = {"\0"};
  char SName[7][N] = {
  {"Aiden"},
  {"Alice"},
  {"Bill"},
  {"Bob"},
  {"Charles"},
  {"Cynthia"},
  {"Dahlia"}
  };
  
  printf("\n\nEnter a name to search for: ");
  fgets(name, sizeof(name), stdin);
  name[strlen(name) - 1] = '\0';  //remove the newline from name

  i = DoBinarySearch(name, SName, rows);
  if(i > -1)
    printf("\nFound it: %s", SName[i]);
  else
    printf("\nThat name could not be found.");

  name[0] = '\0';


  i = getchar(); 
  printf("\n\n\t\t\t    press enter when ready");
  return 0;

}
int DoBinarySearch(char name[], char SName[][N], int rows)
{
  int Middlepoint, result;
  int LowerB= 0;
  int UpperB= rows-1;
  //printf ("\nBinary search not ready! Complete it\n");
  while (UpperB >= LowerB)
  {
    Middlepoint=(LowerB + UpperB)/2;
    result = strcmp(name, SName[Middlepoint]);
    if(result < 0)
      UpperB = Middlepoint-1;
     else if(result==0) 
            return Middlepoint;
     else
         LowerB = Middlepoint + 1;
  }
  return -1; //not found
}

When I had the strcmp() ... in the earlier code, I meant for you to finish filling in the ... with your actual array names. ;)

[emmas4impact]

Thanks so much!! its also work with the pointer. but please i need a little explanation if i want to modify the list. what will i do? i mean creating another function for modify.

[Adak]

A modify function has 3 parts:

1) You have to ask which student name they want to modify and
put that new name, into a small auxiliary char array.

2) You have to then call a search function to see if that name exists, and if so, what is the index number. Binary search does that, and any search can do it, also.

3) Then strcpy() the new name, into the array[], at the index that the search function gave you.

Anything you can do by any other means in an array, you can also do with pointers. It just loses clarity for most people, when you start working with pointers.

NOTE: If you add a name to the array being searched by Binary Search, that name has to either be in already sorted order (not likely), or the array has to be resorted, or don't sort the names, but sort an auxiliary array of ints or pointers, and use that to work with the array[] in the binary search function. A binary search only works if the data is in sorted order (as it see's it).

[emmas4impact]

Thanks i appreciate that a lot here is what i did:

else if (strcmp(czCmds[3],czCommand)==0 ||
		   czCmds[3][0]==czCommand[0]) //modify
		{
	       //printf("\nNot ready to modify...");
		   
		   printf("\nModifying: Give the name: ");
		   GetAnsw(name);
		   //printf("... repeated: %s ", name);
		   FindSequentially(name, czStudentName, N, &iFound);
		   //printf("\nreturn code from finding: %d", iFound);
		   if (iFound>0){ //old one exists, no insert
				  printf("\nGive the name you will like to change it to: ");
				  GetAnsw(name);
				  strcpy( name,czStudentName[N]); 
				 
				  printf("\nGive the ID: ");
				  GetAnsw(name);
				  iStudID[N]= atoi(name);	
				  N= N +1;
				  printf ("\nModified! There are now %d records!", N);
			   
				  
		   }
		   else
			//no found,  the proper place for it is at the end
		   {
		      printf("\nThe name does not exit! Try again"); 
			      
		   }

But instead of modifying the name is inserting a new name in the list.

[Adak]

your strcpy parameters are backwards:

strcpy( destination, source).

How are you handling the sort requirements for the names, so Binary search will keep working?

[emmas4impact]

Thanks a lot. Now i have don the modification but i have a problem. how can i make the program work so that in front of each name it will tell if the name is male or female. And how to detect if there are duplicates of names in the list.

[Adak]

An easy way to find duplicates is to sort the list of names, that puts the duplicates right next to each other in the list. Then run through the list and if list == list[i+1], then you have a duplicate. Stop the search at one less than normal, or else list[i+1] will be out of bounds of the size of the array.

If you need to print up other info on these people, then you need to include that info and put it into a struct along with their other pieces of info, (recommended). If you haven't had structs yet, then you can use parallel arrays for this (works, but it's not nearly as elegant).

Let's start a new thread with a better topic, if you want help with structs or parallel arrays. "Binary Search" is misleading, and that problem is solved.