Like Tree1Likes
  • 1 Post By ssharish2005

binsearch function c programming language book

This is a discussion on binsearch function c programming language book within the C Programming forums, part of the General Programming Boards category; Hi, the function binsearch doesn't work properly, i dont know why, it doesn't find the word "int" in the array, ...

  1. #1
    Registered User blob84's Avatar
    Join Date
    Jun 2010
    Posts
    46

    binsearch function c programming language book

    Hi, the function binsearch doesn't work properly, i dont know why, it doesn't find the word "int" in the array, with the simplest, but slowest search function it find it.

    Code:
    #include <stdio.h>
    #include <ctype.h>
    #include <string.h>
    #define MAXWORD 100
    
    struct key {
    	char *word;
        	int count;
    } keytab[] = {
    	"int", 0,
    	"for", 0,
        	"break", 0,
        	"case", 0,
        	"char", 0,
        	"const", 0,
        	"continue", 0,
        	"default", 0,
        	"unsigned", 0,
        	"void", 0,
        	"volatile", 0,
        	"while", 0
    };
    
    #define NKEYS (sizeof keytab / sizeof(struct key))
    
    int binsearch(char *, struct key *, int);
    int search(char *word, struct key tab[], int n);
    
    /* count C keywords */
    int main(void)
    {
    	struct key *p = keytab;
    	char *word = "ddog";
    	int n;
    	//n = search(word, p, NKEYS);
    	n  = binsearch(word, p, NKEYS);
    	printf("n=%d\n", n);
    
        	return 0;
    }
    /* binsearch: find word in tab[0]...tab[n-1] */
    int binsearch(char *word, struct key tab[], int n)
    {
        int cond;
        int low, high, mid;
        low = 0;
        high = n - 1;
        while (low <= high) {
            mid = (low+high) / 2;
    	cond = strcmp(word, tab[mid].word); printf("cond=%d\n", cond);
            if (cond < 0)
                 high = mid - 1;
            else if (cond > 0)
                 low = mid + 1;
            else
                 return mid;
        }
        return -1;
    }
    
    int search(char *word, struct key tab[], int n)
    {
    	for ( n-=1; n >= 0; n--) {
    		if (!strcmp(word, tab[n].word))
    			return n;
    	}
    	return -1;
    }

  2. #2
    Registered User blob84's Avatar
    Join Date
    Jun 2010
    Posts
    46
    oh!
    The keyword must be in lexicographics order or binsearch can't compare the right string.

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    	cond = strcmp(word, tab[mid].word); printf("cond=%d\n", cond);
            if (cond < 0)
                 high = mid - 1;
            else if (cond > 0)
                 low = mid + 1;
            else
                 return mid;
    I just gave this a quick glance, but this is really only going to work if tab is sorted alphabetically. If I'm looking at this right, you are expecting the return results from strcmp to decide what way to move through the table.


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

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,437
    Because a pre-condition of binsearch is that the array is SORTED by the comparison function you're using to do the search with.
    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 ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,682
    >Hi, the function binsearch doesn't work properly, i dont know why, it doesn't find the word "int" in the array, with the simplest, but slowest search function it find it.
    Because your searching for something different

    Code:
    char *word = "ddog";   /* shouldn't this be "int" is your searching for "int" */
    ssharish
    quzah likes this.
    Life is like riding a bicycle. To keep your balance you must keep moving - Einstein

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. a mistake in the c programming language book.wtf?
    By KidMan in forum C Programming
    Replies: 9
    Last Post: 01-17-2006, 03:33 AM
  2. The C++ Programming Language(book) exercise troubles
    By Daniel Primed in forum C++ Programming
    Replies: 11
    Last Post: 11-07-2005, 12:56 AM
  3. What's the Difference Between a Programming Language and a Scripting Language?
    By Krak in forum A Brief History of Cprogramming.com
    Replies: 23
    Last Post: 07-15-2005, 04:46 PM
  4. Question about the book "The C Programming Language"
    By caduardo21 in forum C Programming
    Replies: 4
    Last Post: 05-15-2005, 01:22 PM
  5. 1 book; 1 language
    By CodeMonkey in forum C++ Programming
    Replies: 4
    Last Post: 03-17-2002, 07:16 PM

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