As you will solve more complex problems, you will find that searching for values

Question

As you will solve more complex problems, you will find that searching for values in arrays becomes a crucial operation. In this part of the lab, you will input an array from the user, along with a value to search for. Your job is to write a C++ program that will look for the value, using the linear (sequential) search algorithm. In addition, you should show how many steps it took to find (or not find) the value, and indicate whether this was a best or worst case scenario (... remember the lecture). You may refer to the pseudo-code In the lecture, but remember that the details of the output and error conditions are not specified there. Also, note that in pseudo-code arrays are sometimes defined with Indices 1 to N, whereas In C++ the indexes span from 0 to N-l.

Explanation / Answer

Program in C++

#include<iostream>
using namespace std;

int main()
{

int array_Size,i,j;
int element_To_Search;

cout<<"Please enter the array size desired: "<<endl;
cin>>array_Size;

int array[array_Size];

for(i=0;i<array_Size;i++) //Fill array using user's data
{
   cout<<"Please enter "<<i<<"th index array element "<<endl;
    cin>>array[i];
}

cout<<"Please enter element to search in array"<<endl;
cin>>element_To_Search;

for(j=0;j<array_Size;j++)
{
   if(element_To_Search==array[j])
   {
       cout<<"Element found in array's index no.' : "<<j+1<<endl;
       break;
    }
}

if(j ==array_Size)
{
   cout<<"Element is not found in array, and it take "<<array_Size<<" iterations to search the element"<<endl;
}
else
{
   cout<<"It taken "<<j<<" iterations to search the element"<<endl;
}

}

Worst Case Scenario

In above program, if we search for the element that is not present in the array then we have to iterate till the last element of the array, It will be the worst case scenario of linear search. worst case time complexity will be O(n)

Best Case Scenario

In the above program, if we get the element that we need to search on first index place then it will be the best case scenario. In this case best case time complexity will be O(1)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.