Like Tree1Likes
  • 1 Post By anduril462

Need help with binary search

This is a discussion on Need help with binary search within the C Programming forums, part of the General Programming Boards category; Hello all, I am currently writing a program that deals with binary searching.To give you some background on the program, ...

  1. #1
    Registered User
    Join Date
    Dec 2012
    Posts
    28

    Need help with binary search

    Hello all, I am currently writing a program that deals with binary searching.To give you some background on the program, a file is opened, loaded into an array.From there, the string the user enters is passed to a function that searches to see if that word exists within the file. Now, I can't seem to get it to work. It's returning false everytime the function executes.here is the code I have

    Code:
    int first=0;
    int last =0;
    word findword;
    last=dictionary.size-1;
    int middle=0;
    int position=-1;
     
    
    findword.found=false;
     
      while(findword.found==false && first<=last)
     {
      middle=(first+last)/2;
      if (strcmp(s,dictionary.words[middle].letters)==0)
      
      
        {
         findword.found=true;
         position=middle;
         return true;
        }
       else if (dictionary.words[middle].letters>s)
       {
         last=middle-1;
       }
       else
       first=middle+1;
       }
       return false;
      }
    Last edited by saldar05; 01-07-2013 at 07:08 PM.

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,309
    Provide all the relevant code, and post the real code, not some snippet you dredged out of your memory. Make sure it's properly indented and formatted, so we can actually read it.

  3. #3
    Registered User
    Join Date
    Dec 2012
    Posts
    28
    sorry...that should be better...I hope

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Your function lost me. Try it like this:

    Code:
    #include <stdio.h>
    #include <string.h>
    
    int binarySearch(char words[6][30], char target[6]);
    
    int main(void) {  
       int i;
       char words[6][30] = {
       {"Alfa"},{"Bravo"},{"Charlie"},{"Delta"},{"Echo"},{"Foxtrot"}};
       char target[30];
    
       printf("Enter the word you are searching for: ");
       fflush(stdout);
       scanf("%s",target);
       
       i=binarySearch(words,target);
    
       if(i>-1)  //zero is a legitimate array index
          printf("Found it, index %d in the array\n",i);
       else
          printf("Target word: %s was not found in the list\n",target);
       
      
    
       return 0;
    }
    int binarySearch(char words[6][30], char target[30]) {
       int i, lo=0,hi=5,mid;
       
       while(lo<=hi) {
          mid = (lo + hi)/2;
          i=strcmp(words[mid],target);
                  //helpful for debugging:
                  //printf("i:%d  mid:%d  words[mid]: %s\n",i,mid,words[mid]); getchar();
          if(i>0) {
             hi=mid-1;
          }else if(i<0) {
             lo=mid+1;
          }else
             return mid; //target was found, this is it's index
       }
       return -1; //target was not found
    
    }
    Last edited by Adak; 01-07-2013 at 09:03 PM.

  5. #5
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,309
    Adak has a nice example for you, that includes a fix to the problem you had, but just to be clear about why your code wasn't working:
    Code:
    else if (dictionary.words[middle].letters>s)
    That is not a valid comparison. You don't compare strings with ==, !=, <, <=, > or >=. You should be looking at the result of strcmp to see if one string is greater than the other. Save the result in a variable (to avoid calling it multiple times) and use that in your if/else if statements. Something like:
    Code:
    int comp_result = strcmp(s, dictionary.words[middle].letters);
    if (comp_result == 0)
        // found it
    else if (comp_result < 0)  //s is less than the dictionary word
        last = middle - 1;
    else
        first = middle + 1;
    Salem likes this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree-search method help?
    By shocklightning in forum C++ Programming
    Replies: 5
    Last Post: 03-25-2012, 10:57 PM
  2. Difference Between A Linear Search And Binary Search
    By ImBack92 in forum C Programming
    Replies: 4
    Last Post: 05-12-2011, 08:47 AM
  3. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 01:12 PM
  4. Search Engine - Binary Search Tree
    By Gecko2099 in forum C Programming
    Replies: 9
    Last Post: 04-17-2005, 02:56 PM
  5. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 09:18 AM

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