Thread: Linear and binary search in c functions

  1. #1
    Registered User
    Join Date
    Feb 2015
    Posts
    45

    Linear and binary search in c functions

    hi i have this HW
    it partially works ..
    the program must ask the user for 10 positive integers in ascending order.. then search for a number given by user ... search must be accomplished through two functions : linear and binary

    so far i have 3 problems :
    1- i keep getting two warning
    2- linear search is not working although the algorithm is fine
    3- binary search is printing the wrong"search" number.

    here is my code
    Code:
    #include<stdio.h>
    
       int searchLinear(int s,int *list, int n); //definition of first function..
       int searchBinary(int s,int *list, int n); //definition of second function..
    
    
    int main(void)
    {
      int number[10];
       int i,search;
       int count=10;
       
       printf("Please enter 10 positive numbers in ascending order:\n");
       
          for(i=0;i<count;i++)
       
       scanf("%d\n",&number[i]);
       
       
       
       printf("What number you want to search for ? :\n");
       scanf("%d\n",&search);
       
       searchLinear(search, number,count);
       searchBinary(search, number,count);
       
       return 0;
       }
       
      
       
    int searchLinear(int s,int *list, int n)
      {
    
       int i;
       
       for(i=0;i<10;i++)
       
       if (list[i]==s)
       
        printf("%d is found at location %d\n", s,i+1);
        
        else
         
        return -1; 
        
       }
    
    int searchBinary(int s,int *list,int n)
    {
      int  first = 0;
      int  last = n - 1;
      int  middle = (first+last)/2;
     
       while( first <= last )
       {
          if ( list[middle] < s )
            first = middle + 1;    
          else if ( list[middle] == s ) 
          {
            printf("%d found at location %d.\n", s, middle+1);
             break;
          }
          else
             last = middle - 1;
     
          middle = (first + last)/2;
       }
       if ( first > last )
       
          printf("Not found! %d is not present in the list.\n", s);
    
    }
    
    


    appreciate any help ... thank you...

  2. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    Let me guess: It warns you because both functions don't always return something. Remember that if a functions ends its execution before a "return" statement, it returns garbage to the caller.
    Devoted my life to programming...

  3. #3
    Registered User
    Join Date
    Feb 2015
    Posts
    45
    Quote Originally Posted by GReaper View Post
    Let me guess: It warns you because both functions don't always return something. Remember that if a functions ends its execution before a "return" statement, it returns garbage to the caller.


    yes you are RIGHT !
    i got rid of warnings now .. but still have the other problems

    thanks !!
    Last edited by Hana Nasser; 03-10-2015 at 12:51 PM.

  4. #4
    Registered User
    Join Date
    Feb 2015
    Posts
    45
    this is the last modification :
    Code:
    #include<stdio.h>
    
    int searchLinear(int s,int *list, int n); //definition of first function..
    int searchBinary(int s,int *list, int n); //definition of second function..
    
    
    int main(void)
    {
        int number[10];
        int i,search;
        int count=10;
    
        printf("Please enter 10 positive numbers in ascending order:\n");
    
        for(i=0; i<count; i++)
            scanf("%d\n",&number[i]);
    
        printf("What number you want to search for ? :\n");
        scanf("%d\n",&search);
    
        searchLinear(search, number,count);
        searchBinary(search, number,count);
    
        return 0;
    }
    
    int searchLinear(int s,int *list, int n)
    {
        int i;
    
        for(i=0; i<10; i++)
            if (list[i]==s)
                printf("%d is found at location %d\n", s,i+1);
            else
                printf("%d is not found\n",s);
    
        return -1;
    }
    
    int searchBinary(int s,int *list,int n)
    {
        int  first = 0;
        int  last = n - 1;
        int  middle = (first+last)/2;
    
        while( first <= last )
        {
            if ( list[middle] < s )
                first = middle + 1;
            else if ( list[middle] == s )
            {
                printf("%d found at location %d.\n", s, middle+1);
                break;
            }
            else
                last = middle - 1;
    
            middle = (first + last)/2;
        }
    
        if ( first > last )
            printf("Not found! %d is not present in the list.\n", s);
    
        return -1;
    }
    when i search for 100 (which is inside the array)
    it search for 102 !!
    and prints "not found"
    why it's not searching for the exact number i entered ?[/FONT]
    Last edited by Salem; 03-10-2015 at 01:56 PM. Reason: fixed font / colour abuse

  5. #5
    Registered User
    Join Date
    Jun 2011
    Posts
    4,513
    What input are you giving the program?

    Code:
    scanf("%d\n",&number[i]);
    
    // ...
    
    scanf("%d\n",&search);
    Try taking the '\n' out of the format strings there.

  6. #6
    Registered User
    Join Date
    Feb 2015
    Posts
    45
    Quote Originally Posted by Matticus View Post
    What input are you giving the program?

    Code:
    scanf("%d\n",&number[i]);
    
    // ...
    
    scanf("%d\n",&search);
    Try taking the '\n' out of the format strings there.
    this is what i get .. searching for number 3

    Please enter 10 positive numbers in ascending order:
    ¼¼§Ï1
    ¼¼§Ï2
    ¼¼§Ï3
    ¼¼§Ï4
    ¼¼§Ï5
    ¼¼§Ï6
    ¼¼§Ï7
    ¼¼§Ï8
    ¼¼§Ï9
    ¼¼§Ï10
    ÏϧÏWhat number you want to search for ? :
    ¼¼§Ï3
    ÏϧÏ3 is not found
    ÏϧÏ3 is not found
    ÏϧÏ3 is found at location 3
    ÏϧÏ3 is not found
    ÏϧÏ3 is not found
    ÏϧÏ3 is not found
    ÏϧÏ3 is not found
    ÏϧÏ3 is not found
    ÏϧÏ3 is not found
    ÏϧÏ3 is not found
    ÏϧÏ3 found at location 3.
    ÏϧÏ

    i got rid of \n as you advised ..apparently sth is wrong i can't find it


  7. #7
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    What is the value returned by the search functions supposed to be?

    Hint: Returning a -1 is likely supposed to be the value to indicate the search failed.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  8. #8
    Registered User
    Join Date
    Feb 2015
    Posts
    45
    Quote Originally Posted by stahta01 View Post
    What is the value returned by the search functions supposed to be?

    Hint: Returning a -1 is likely supposed to be the value to indicate the search failed.

    Tim S.
    you are right , it must return -1 and a msg says number isn't found if the search failed ... and return the location of the number if number was found.

  9. #9
    Registered User
    Join Date
    Feb 2015
    Posts
    45
    i'm still getting wrong output .. if any one could help me fixing the problem..

    input example
    Please enter 10 positive numbers in ascending order:
    ¼¼§Ï12
    ¼¼§Ï14
    ¼¼§Ï20
    ¼¼§Ï30
    ¼¼§Ï36
    ¼¼§Ï100
    ¼¼§Ï102
    ¼¼§Ï200
    ¼¼§Ï201
    ¼¼§Ï202
    ÏϧÏWhat number you want to search for ? :
    ¼¼§Ï100
    ÏϧÏ100 is not found
    ÏϧÏ100 is not found
    ÏϧÏ100 is not found
    ÏϧÏ100 is not found
    ÏϧÏ100 is not found
    ÏϧÏ100 is found at location 6
    ÏϧÏ100 is not found
    ÏϧÏ100 is not found
    ÏϧÏ100 is not found
    ÏϧÏ100 is not found
    ÏϧÏ100 found at location 6.
    ÏϧÏ

    why i keep getting "100 is not found"


  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > why i keep getting "100 is not found"
    Because you told it to do it.
    Because you put this INSIDE the loop doing the searching.

    Compare with your other function, which only prints things after the loop is run.
    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.

  11. #11
    Registered User
    Join Date
    Feb 2015
    Posts
    45
    Quote Originally Posted by Salem View Post
    > why i keep getting "100 is not found"
    Because you told it to do it.
    Because you put this INSIDE the loop doing the searching.

    Compare with your other function, which only prints things after the loop is run.
    i tried to use curly braces
    Code:
     {}
    before and after the print statement ... i tried using break; statement nothing work !
    can you please be more specific and tell me what to do to avoid that ? thank you ..

  12. #12
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,949
    Quote Originally Posted by Hana Nasser
    Code:
    int searchLinear(int s,int *list, int n)
    {
        int i;
    
        for(i=0; i<10; i++)
            if (list[i]==s)
                printf("%d is found at location %d\n", s,i+1);
            else
                printf("%d is not found\n",s);
    
        return -1;
    }
    Each iteration prints something, either found or not found. That is what Salem is referring to. Compare this function with your search binary function and note where the difference is.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  13. #13
    Registered User
    Join Date
    Feb 2015
    Posts
    45
    Quote Originally Posted by AndrewHunter View Post
    Each iteration prints something, either found or not found. That is what Salem is referring to. Compare this function with your search binary function and note where the difference is.
    i tried using break statement after each printf statement
    Code:
    for(i=0;i<10;i++)
       if (list[i]==s)
       {
        printf("%d is found at location %d\n", s,i+1);
        break;
        }
        else
        {
         printf("%d is not found\n",s);
         break;
         }
        return -1; 
       }
    


    searching for number 50 (which is in location 5)
    gives me this as an output:
    Code:
    
    
    Code:
    ÏWhat number you want to search for ? :
    ¼¼§Ï50
    ÏϧÏ50 is not found
    ÏϧÏ50 found at location 5.
    ÏϧÏ
    


    i understand what you and salem trying to say but i tried out every possible
    solution

  14. #14
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,949
    So why do you think that is? What happens in your loop if the number is not found? Right now your for loop basically says:
    Code:
    for(all numbers in array)
    {
        if( number is found)
        {
              print found
              stop searching
        }
        else number is not found
        {
              print not found
              stop searching
        }
    }
    Is this the logic you really want?
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  15. #15
    Registered User
    Join Date
    Feb 2015
    Posts
    45
    Quote Originally Posted by AndrewHunter View Post
    So why do you think that is? What happens in your loop if the number is not found? Right now your for loop basically says:
    Code:
    for(all numbers in array)
    {
        if( number is found)
        {
              print found
              stop searching
        }
        else number is not found
        {
              print not found
              stop searching
        }
    }
    Is this the logic you really want?
    i think so .. but apparently sth is wrong since it's not working in this case.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linear and binary search!!
    By ari01 in forum C++ Programming
    Replies: 1
    Last Post: 02-06-2014, 12:12 AM
  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. no. of comparisons in linear/binary search
    By alice in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 06-05-2004, 10:55 PM
  4. binary search or linear search
    By vajira in forum C Programming
    Replies: 0
    Last Post: 06-05-2003, 12:42 PM