Linear Search Problem

This is a discussion on Linear Search Problem within the C++ Programming forums, part of the General Programming Boards category; Hi, If anyone could help me with where I've gone wrong with the linear search below it would be greatly ...

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

    Linear Search Problem

    Hi, If anyone could help me with where I've gone wrong with the linear search below it would be greatly appreciated.

    Code:
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    void binarySearch(const vector<int> &numbers, int value);
    void linearSearch(const vector<int> &numbers, int value);
    
    int main()
    {
       vector<int> numbers;
      
       for (int i=0; i<16; i++) numbers.push_back(i);
    
       cout << "Searching for -1 in numbers using linear search\n";
       linearSearch(numbers, -1);
       cout << "Searching for -1 in numbers using binary search\n";
       binarySearch(numbers, -1);
    
       cout << "\nSearching for 0 in numbers using linear search\n";
       linearSearch(numbers, 0);
       cout << "Searching for 0 in numbers using binary search\n";
       binarySearch(numbers, 0);
    
       cout << "\nSearching for 7 in numbers using linear search\n";
       linearSearch(numbers, 7);
       cout << "Searching for 7 in numbers using binary search\n";
       binarySearch(numbers, 7);
    
       cout << "\nSearching for 11 in numbers using linear search\n";
       linearSearch(numbers, 11);
       cout << "Searching for 11 in numbers using binary search\n";
       binarySearch(numbers, 11);
    
       cout << "\nSearching for 15 in numbers using linear search\n";
       linearSearch(numbers, 15);
       cout << "Searching for 15 in numbers using binary search\n";
       binarySearch(numbers, 15);
    
       cout << "\nSearching for 22 in numbers using linear search\n";
       linearSearch(numbers, 22);
       cout << "Searching for 22 in numbers using binary search\n";
       binarySearch(numbers, 22);
    
       return 0;
    }
    
    void binarySearch(const vector<int> &numbers, int value)
    {
       int step = 1, left = 0, right = numbers.size()-1, mid;
    
       while (left <= right)
       {
          mid = (left + right) / 2;
          if (numbers[mid] == value)
          {
             cout << "Number found after " << step << " steps\n";
             return;
          }
          else if (numbers[mid] < value)
             left = mid+1;
          else
             right = mid-1;
          step++;
       }
       cout << "Number not found after " << step << " steps\n";
    }
    
    void linearSearch(const vector<int> &numbers, int value)
    {
       // use linear seach to find value in numbers 
       // print the number of steps it takes to find, or not find, value
    
       int step = 1;
       int index;
       int length = numbers.size();
    
       for (index = 0; index < length; index++)
       {
          if (numbers[index] == value)
          {
             cout << "Number found after " << step << " steps\n";  
          }
          step++;
       }
       cout << "Number not found afer " << step << " steps\n";
    }

  2. #2
    the hat of redundancy hat nvoigt's Avatar
    Join Date
    Aug 2001
    Location
    Hannover, Germany
    Posts
    3,139
    Maybe you should stop, leave or break your loop, after you found the number you were looking for.
    hth
    -nv

    She was so Blonde, she spent 20 minutes looking at the orange juice can because it said "Concentrate."

    When in doubt, read the FAQ.
    Then ask a smart question.

  3. #3
    Registered User
    Join Date
    Aug 2006
    Posts
    127
    Worked it out. Should've used return not break and my count was in the wrong place.

    Thanks.
    Last edited by Taka; 04-30-2009 at 04:31 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. problem in binary search
    By LINUX in forum C++ Programming
    Replies: 1
    Last Post: 01-28-2009, 07:50 AM
  2. Binary Search Tree scope? problem
    By tms43 in forum C++ Programming
    Replies: 5
    Last Post: 11-01-2006, 09:13 PM
  3. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 09:18 AM
  4. Binary trees search problem...
    By Umoniel in forum C Programming
    Replies: 2
    Last Post: 02-22-2004, 01:29 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

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