k1ber k1ber - 1 month ago 17
C++ Question

Linear search algorithm

The goal of my program is to find the number entered by user in an array of integers (array was created automatically), and to show the index of this number (or numbers, if they occurs several times). It works correctly when the desired number occurs only once in array. For example, if there is an array

7 8 0 4 2 7 2


and user entered "8", the output of program will be

Index of the number you entered is: 2


But when we have array:

0 5 3 9 3 7 2


And the user entered "3", the output will be

Index of the number you entered is: 3


And I wonder how to make the program include second "3" number which has index 5. The code of program:

#include <iostream>
#include <ctime>
#include <stdlib.h>

using namespace std;

int i, N;

int LinearSearch(int Array[], int searchValue)
{
for (i=0; i<N; i++)
{
if (Array[i]==searchValue)
return i;
}
return -1;
}

int main()
{
int searchValue, Array[1000];

cout<<"Size of array: ";
cin>>N;

cout<<"Array: ";
for (i=0; i<N; i++)
{
Array[i]=rand()%10;
cout<<Array[i]<<" ";
}

cout<<"Search value: ";
cin>>searchValue;

if (LinearSearch(Array, searchValue)==1)
cout<<"\nIndex of the number you entered is: "<<LinearSearch(Array, searchValue)+1;
else
cout<<"\nNothing found";
}

Answer

Because you return from the search function as soon as the value is located:

for (i=0; i<N; i++)
{
    if (Array[i]==searchValue)
        return i; // <-- as soon as we get here, we break the loop
}

therefore, you will get the first position in which searchValue is located, which is 2 (0-based). Thus, you get 2+1 = 3. To get the last one, you will have to remove the early exit, and keep the current index in a variable, like this:

int LinearSearch(int Array[], int searchValue) {
    int index = -1;

    for (i = 0; i < N; i++) {
        if (Array[i]==searchValue) {
            index = i;
        }
    }

    return index;
} 
Comments