Thread: Logical errors with seach function

  1. #1
    Registered User
    Join Date
    Aug 2006
    Posts
    127

    Logical errors with seach function

    I am working on a homework assignment to make a program that searches using binary and linear searches. It compiles but the logical errors mean it doesn't work at all. I'm not really sure where I've gone wrong so any help would be great. Thanks.

    Code:
    #include <stdio.h>
    
    #define SIZE 15
    
    void binarySearch(int numbers[], int value);
    void linearSearch(int numbers[], int value);
    
    int main()
    {
       int numbers[] =  { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, };
    
       printf("Searching for -1 in numbers using linear search\n");
       linearSearch(numbers, -1);
       printf("Searching for -1 in numbers using binary search\n");
       binarySearch(numbers, -1);
    
       printf("\nSearching for 0 in numbers using linear search\n");
       linearSearch(numbers, 0);
       printf("Searching for 0 in numbers using binary search\n");
       binarySearch(numbers, 0);
    
       printf("\nSearching for 7 in numbers using linear search\n");
       linearSearch(numbers, 7);
       printf("Searching for 7 in numbers using binary search\n");
       binarySearch(numbers, 7);
    
       printf("\nSearching for 11 in numbers using linear search\n");
       linearSearch(numbers, 11);
       printf("Searching for 11 in numbers using binary search\n");
       binarySearch(numbers, 11);
    
       printf("\nSearching for 15 in numbers using linear search\n");
       linearSearch(numbers, 15);
       printf("Searching for 15 in numbers using binary search\n");
       binarySearch(numbers, 15);
    
       printf("\nSearching for 22 in numbers using linear search\n");
       linearSearch(numbers, 22);
       printf("Searching for 22 in numbers using binary search\n");
       binarySearch(numbers, 22);
    
       return 0;
    }
    
    void binarySearch(int numbers[], int value)
    {
       int step = 1, left = 0, right = SIZE-1, mid;
    
       while (left < right)
       {
          mid = (left + right) / 2;
          if (numbers[mid] == value)
          {
             printf("Number found after %d steps\n", step);
             return;
          }
          else if (numbers[mid] < value)
          {
             left = mid+1;
             step++;
          }
          else
             right = mid-1;
             step++;   
       }
       printf("Number not found after %d steps\n", step);
    }
    
    void linearSearch(int numbers[], int value)
    {
       /* Use linear search to find value in numbers.
          Print the number of steps it takes to find or not find value
       */  
    
       int steps, i;
    
       for (i=0; i < SIZE; i++)
       {
          if (value == numbers[i])
          {
              printf("Number found after %d steps\n");
              return;
          }
          printf("Number not found after %d steps\n");
       }
    }
    This was the result I got when I tested it:
    Your test result
    Searching for -1 in numbers using linear search
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Searching for -1 in numbers using binary search
    Number not found after 4 steps

    Searching for 0 in numbers using linear search
    Number found after 0 steps
    Searching for 0 in numbers using binary search
    Number not found after 4 steps

    Searching for 7 in numbers using linear search
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number found after 0 steps
    Searching for 7 in numbers using binary search
    Number found after 1 steps

    Searching for 11 in numbers using linear search
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number found after 0 steps
    Searching for 11 in numbers using binary search
    Number found after 3 steps

    Searching for 15 in numbers using linear search
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Searching for 15 in numbers using binary search
    Number not found after 7 steps

    Searching for 22 in numbers using linear search
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Number not found after 0 steps
    Searching for 22 in numbers using binary search
    Number not found after 7 steps

    Expected result
    Searching for -1 in numbers using linear search
    Number not found after 16 steps
    Searching for -1 in numbers using binary search
    Number not found after 5 steps

    Searching for 0 in numbers using linear search
    Number found after 1 steps
    Searching for 0 in numbers using binary search
    Number found after 4 steps

    Searching for 7 in numbers using linear search
    Number found after 8 steps
    Searching for 7 in numbers using binary search
    Number found after 1 steps

    Searching for 11 in numbers using linear search
    Number found after 12 steps
    Searching for 11 in numbers using binary search
    Number found after 2 steps

    Searching for 15 in numbers using linear search
    Number found after 16 steps
    Searching for 15 in numbers using binary search
    Number found after 5 steps

    Searching for 22 in numbers using linear search
    Number not found after 16 steps
    Searching for 22 in numbers using binary search
    Number not found after 6 steps

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Expected result
    Searching for -1 in numbers using linear search
    Number not found after 16 steps
    Since your list is sorted, it should know on the first match that -1 isn't in the list, since the first element is the lowest.
    Code:
    if (value == numbers[i])
          {
              printf("Number found after %d steps\n");
              return;
          }
          printf("Number not found after %d steps\n");
    You never increment 'steps'. You never supply arguments for your specifiers for printf. Also, you apparently completely ignore your compiler as it screams at you for doing so...


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

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    In your binary search, you can't find 15, because it's the 16th number in your number array.
    But you've defined SIZE as 15.

    0 through 15 == 16 numbers.

    In the array initialization, you should remove the comma after the 15. Commas separate entries, they don't go after the last one in the set.

    And your problem with the linear search, you have already been given.

    That should get things searching aright.

    Adak

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by Adak
    In the array initialization, you should remove the comma after the 15. Commas separate entries, they don't go after the last one in the set.
    They can go after the last one. It has no effect. It's allowed by the standard.


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

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by quzah
    They can go after the last one. It has no effect. It's allowed by the standard.


    Quzah.
    Thanks for the correction, Quzah.

    Adak

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. dllimport function not allowed
    By steve1_rm in forum C++ Programming
    Replies: 5
    Last Post: 03-11-2008, 03:33 AM
  2. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  3. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  4. Calling a Thread with a Function Pointer.
    By ScrollMaster in forum Windows Programming
    Replies: 6
    Last Post: 06-10-2006, 08:56 AM
  5. Replies: 3
    Last Post: 03-04-2005, 02:46 PM