How to fix this in Linear Search?

[jomnepo]

This is my program code for my linear search program. The condition of my professor was to generate a random set of numbers and the user should declare the number of numbers in the array.

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
    int choice;
    cout<< "[1]Linear Search\n[2]Binary Search\nChoose your searching algorithm: ";
    cin>> choice;

    if (choice==1)
    {
    int size;
    cout<< "Enter size of array:";
    cin>> size;

    srand(time(0));
    const int N = size;
    int search, array[N];

    for(int inc=0; inc<N ; inc++)
    {
        array[inc]=(rand()%N);
        cout<< array[inc] << " ";
    }
    cout<< "\n\nWrite a number to search for: ";
    cin>> search;

    while (search !=-1)
    {

        int inc=0;
        while (array[inc] != search || inc==N)
          {
           inc++;
          }

                if(array[inc] == search)
                {
                    cout << "The key " << search;
                    cout << " is found on the index " << inc;
                    cout << "." << endl;

                }
                else
                {
                    cout<< "\nSorry, I can't seem to find it." << endl;
                    break;
                }
    }
    }


    else if (choice==2)

    {
    int size;
    cout<< "Enter size of array:";
    cin>> size;

    srand(time(0));
    const int N = size;
    int low, high, current, search, array[N];
    srand(time(0));

    for(int inc=0; inc<N ; inc++)
    {
        array[inc]=rand()%65536;
    }

    for(int inc=0; inc<N-1; inc++)
        for(int j=inc+1; j<N; j++)
        if(array[inc]>array[j])
    {

        int tmp=array[inc];
        array[inc]=array[j];
        array[j]=tmp;

    }
    cout << endl <<endl;

    for(int inc=0; inc<N; inc++)
        cout <<array[inc] << " ";

    cout <<endl;

    cout<< "\n\nWrite a number to search for:";
    cin>> search;

    while (search!=-1)
    {
    low =0;
    high = N-1;
    while (low<=high)
    {
        current=(low+high)/2;
        if(search > array[current])
            low = current+1;
        else if(search < array[current])
            high = current-1;
        else
            break;
    }

    if(array[current]==search)
    {
        cout<< "\nThe key " << search;
        cout << " is found it at index " << current;
        cout<< "." << endl;
        break;
    }

    else
    {
     cout << "\nI can't seem to find it." <<endl;
     break;
    }
    }
    }


    else

    {
    cout<< "Invalid Input!\n";
    }

    cout<< "Thank you for using the program.";
    return 0;
}

When I executed the program, if the key was in the array it executes the statement inside the if. But when I would search for a value that is not in the array, it would still execute the if statement and it says "The key was found in index 19."

PS: There's no problem in my code for the random generation of numbers and the declaration of the number of elements in the array.

[Peter87]

You have a problem with the loop condition going out of bounds.

[jomnepo]

Which loop condition Sir Peter87?

[Peter87]

I'm talking about the loop that do the linear search.

[jomnepo]

I still can't figure out what is wrong. :(

[Chervil]

General comments.
The program is getting too long/complex to keep all the code within main(). The program would be easier to read/understand if it used separate functions for each activity, e.g. allocate and fill array, sort array, linear search, binary search.

Next, arrays in C++must have a size which is a compile-time constant. int array[N]; is not valid in standard C++ because the value of N is not known until run-time. An alternative is to use new/delete.

    int * array = new int [N]; // allocate array  

    delete [] array;  // de-allocate array when finished 

Specific problems with linear search.

1. If the item is not found, this loop will never terminate:

            while (array[inc] != search || inc == N)
            {
                inc++;
            }

One or both conditions will always be true (assuming not found). The subscript inc will exceed the array size N.
This would be better:

    while (array[inc] != search && inc < N)

2. On the other hand, if the item is found, then the surrounding loop will repeat forever

        while (search != -1)

(assuming user didn't ask for -1 as search value).

[Peter87]

Chervil wrote:

This would be better:

    while (array[inc] != search && inc < N)

It would be even better to test inc before accessing the array element, otherwise you will access array[N] which is out of bounds.

    while (inc < N && array[inc] != search)

[Chervil]

Yes, thanks Peter87, you are right.