Linear Search
Let say you have 6 books arranged linearly in any order numbered in the range between (20,50) and your friend wants to check whether you have book number 28 or not?
So in this case what your friend will do?
He/she will check for the first book whether the first book is the book whose book number is 28 or not.
If yes then your friend can say yes you have the book whose number is 28 otherwise he/she will check for the next book in the same manner.
Ok So my friend the searching technique you have just implemented is the linear search.
In linear search you check for the first element whether is it the required element or not. You check for each element which are linearly arranged.
#include <iostream>
using namespace std;
bool LinearSearch(int arr[], int size, int target)
{
for(int i=0;i<size;i++)
{
if(arr[i] == target)
return true;
}
return false;
}
int main()
{
int arr[] = {12,5,10,15,31,20,25,40};
int target = 20, size = 8;
bool ans = LinearSearch(arr, size, target);
if(ans)
cout<<"Targeted element is present in the array";
else
cout<<"Targeted element is not present in the array";
return 0;
}
Output:
Targeted element is present in the array
Time Complexity:
Best Case: O(1)
Average Case: O(n)
Worst Case: O(n)