Embedded Files
Check The Programming Section
In linear search we considered an unordered list, to search an item within the list. It sequentially checks each element of the list until a match is found or the whole list has been searched. If the element is found then its position is displayed. The worst case time complexity for linear search is O(n). n is the number of items in a list.
Step-by-step representation of searching an item 45 sequentially
Time and Space Complexity
Worst case O(n)
Best case O(1)
Average case O(n)
Worst case space complexity is O(1) in iterative approach
Consider an unsorted one-dimenstional array displayed in the image. From this list of item, suppose you wants to search an item 45. So, in linear search, searching is started from the item reside at first index [0] and searching is continue till the search item is found or this process will continue till the last index [9] of the array. But, in this case serached item is 45 and it is present at index 3. So the linear search algorithm will return the index 3.
The required source code is listed below (edit and try):
#include<iostream>
using namespace std;
int linearSearch(int num[], int size, int item){
for(int i=0; i<size;i++){
//comparing each array item with searchItem
if(num[i]==item){
return i;//return the location
}
}
return -1;//if item is not present retrun -1
}
int main(){
int num[] = {10, 23, -1, 45, 67, 90, 12, 78, 2, 9};
int searchItem;
//calculates number of item in the srray
int size = sizeof num / sizeof num[0];
cout<<"Enter an integer to be search :";
cin>>searchItem;
//calling the function
int index = linearSearch(num, size, searchItem);
if(index==-1){
cout<<"The searched item "<<searchItem<<" is not found in the array";
}
else{
cout<<searchItem<<" is found at location "<<index+1;
}
}
Page updated
Google Sites
Report abuse