Thread: Help with binary search

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    11

    Help with binary search

    I need create a binary search that computes and prints the average search cost.

    This is what I have so far..the last part is my sortList. If it is incorrect please help :P

    Thanks

    Code:
    #include <stdio.h>
    #include <string.h>
    #define TRUE 1
    #define FALSE 0
    #define MAXNAMESIZE 32
    #define MAXLISTSIZE 1000
    #define TEST TRUE
    
    int readList(char[][MAXNAMESIZE]);
    void printList(char[][MAXNAMESIZE], int);
    void testSequentialSearch(char[][MAXNAMESIZE], int);
    void writeList(char[][MAXNAMESIZE], int);
    int sequentialSearch(char[][MAXNAMESIZE], int, char[]);
    
    
    
    int main() {
    	
    	
    	int listSize;
    	char nameList[MAXLISTSIZE][MAXNAMESIZE];
    	
    	listSize = readList(nameList); 
    	if (TEST) printList(nameList, listSize);
    	testSequentialSearch(nameList, listSize);
    	if (TEST) printList(nameList, listSize);
    	writeList(nameList, listSize);
    
    	return 0;
    }
    
    int readList(char nameList[][MAXNAMESIZE]) {
    
    	FILE *fp;
    	int length, listSize = 0;
    	char name[MAXNAMESIZE];
    
    	fp = fopen("names.txt", "r"); 
    
    	while (fgets(name, MAXNAMESIZE, fp) != NULL) { 
    		length = strlen(name);
    		if (name[length-1]=='\n') name[length-1] = '\0';
    
    		if (strlen(name)>0) {
    			strcpy(nameList[listSize],name);
    			listSize = listSize + 1;
    		}
    	}
    
    	fclose(fp);
    
    	return listSize;
    }
    
    void printList(char nameList[][MAXNAMESIZE], int listSize) {
    
    		int i;
    		
    		if (listSize == 0) {
    			printf("Empty list\n");
    			return;
    		} else {
    			for (i=0; i<listSize; i++) {
    				printf("&#37;s\n",nameList[i]);
    			}
    		}
    
    		return;
    }
    
    void testSequentialSearch(char nameList[][MAXNAMESIZE], int listSize) {
    	
    	int i, searchCost = 0;
    	float aveSearchCost; 
    
    	for (i=0; i<listSize; i++) {
    		searchCost = searchCost + sequentialSearch(nameList, listSize, nameList[i]);
    	}
    	
    	if (searchCost == 0) aveSearchCost = 0;
    	else aveSearchCost = (float) searchCost/ (float) listSize;
    
    	printf("Average cost of sequential search = %f\n",aveSearchCost);
    	return;
    }
    
    int sequentialSearch(char nameList[][MAXNAMESIZE], int listSize, char targetValue[]) {
    
    	int i, cost = 0;
    
    	if (listSize == 0) {
    		printf("Search failed.\n");
    	} else {
    		for (i=0; i<listSize; i++) {
    			cost = cost + 1;
    			if (strcmp(nameList[i], targetValue)==0) {
    				return cost;
    			}
    		}
    		printf("Search failed.\n");
    	}
    
    	return cost;
    }
    
    void writeList(char nameList[][MAXNAMESIZE], int listSize) {
    
    	FILE *fp;
    	int i = 0;
    
    	fp = fopen("sortedNames.txt","w");
    
    	for (i=0; i<listSize; i++) {
    		fprintf(fp,"%s\n",nameList[i]);
    	}
    
    	fclose(fp);
    
    	return;
    }
    
    void insertionSort(int numbers[], int array_size)
    {
      int i, j, index;
    
      for (i=1; i < array_size; i++)
      {
        index = numbers[i];
        j = i;
        while ((j > 0) && (numbers[j-1] > index))
        {
          numbers[j] = numbers[j-1];
          j = j - 1;
        }
        numbers[j] = index;
      }
    }

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Write a small program that tests your sort function. Once you get it working, add it do your main program.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Apr 2007
    Posts
    11
    Okay thanks.

  4. #4
    Registered User
    Join Date
    Apr 2007
    Posts
    11
    Okay. So I'm having some trouble. What kind of code should I have?

  5. #5
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    One that attempts to do a binary search?
    http://cboard.cprogramming.com/annou...t.php?f=4&a=39

    If you search Google or Wikipedia with "binary search", as well as perhaps looking in a textbook(?) you've at least got a starting point.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  6. #6
    Registered User
    Join Date
    Apr 2007
    Posts
    11
    well I totally suck at programming. I just started a few days ago. It confuses the hell out of me. It would really be appreciated if I could get some code =\

  7. #7
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    is this for a class? i dont think an intro programming class would be doing something like this 'a few days' into it.

    if your very confused, i dont think theres any point in trying to attempt this at this stage. start doing basic programs, perhaps following the tutorials on this website.

    tutorials:
    http://www.cprogramming.com/tutorial.html

    heres a useful link if you want the answer. if you want to learn, i suggest doing what i mentioned above. http://cprogramming.com/discussionar...searching.html

  8. #8
    Registered User
    Join Date
    Apr 2007
    Posts
    11
    It's for a concepts in computer science class. csc-2001. not really sure why he's having us do it..half the class is lost.

  9. #9
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    well he definetly has valid reason to teach it in that class. however i dont think it should be taught in C, if this is an intro/first programming course.

    if youre a CS major, it would be very wise to look at many of the tutorials, and write your own binary search. you dont need to know syntax or any programming language.. just draw boxes on a piece of paper and think how you would search through it, using english or common sense. (its easy once youve done it many times, however may seem difficult to come up with or understand your first few times).

    the 'binary' in 'binary search' means that for each iteration of the search, your spliting the list in half. when the search is first called, you look at the middle element of a list. you then decide whether to look to elements greater than the middle one or less than (which would mean you search the list again, but only the 1st or 2nd half of it). you repeat this until you find the element your looking for.

  10. #10
    Registered User
    Join Date
    Apr 2007
    Posts
    11
    right. we've gone through how the process works..i just don't know how to code it =\

    call me dumb i guess but i'll try to figure it out. thanks for the help.

  11. #11
    Registered User
    Join Date
    Apr 2007
    Posts
    11
    so if i copy the code that's on that link it'll will give me what i need? lol i feel like a complete tool asking for help on this. i've done python and other languages but this is my first time working with C

  12. #12
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    i think a big thing new programmers have difficulty with is that they dont think! by this i mean they just look at all the weird syntax and foreign language of programming and are overwhelmed.

    ive said this to others before, think about it like your teaching a young child how to search through a list. the thing about computers is that they know nothing--they have to be told exactly what to do, when to do it, and how to do it.

    another (very important) thing to note is that for a binary search to work, the list must be sorted, and you must know the length of the list.

    lets say i have this list:
    Code:
    1   2   3   4   5
    this list is sorted. its length is 5. how would come up with a way of telling the computer to find the number '4'? honestly.. get a piece of paper and try and think about it. the first hint is that you start by looking at the element at index (length / 2). when you find a solution, use another list, say '1 2 3' and see if it works again. your solution has to work in every posible case.

    search wikipedia for a description of binary search or elsewhere.

    edit:
    so if i copy the code that's on that link it'll will give me what i need?
    i dont know, will it?
    Last edited by nadroj; 04-26-2007 at 11:00 PM.

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    It's just like the old kids game of "guess the number". (This was before video games came along.)

    Basically, you're just cutting the search space in half, on each incorrect guess.

    Wikipedia should tell you all about it.

    Adak

  14. #14
    Registered User
    Join Date
    Apr 2007
    Posts
    11
    Quote Originally Posted by nadroj View Post
    edit:
    i dont know, will it?
    Good question...I don't know and I don't even know how to test it lol

  15. #15
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    as mentioned above, just try and work it out using the above methods, or search wikipedia page, or wherever you want for how or why it works. or, again, better yet try and think of it yourself!

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