Advanced Linear search Algorithm | c++

March 28, 2020   Algorithm , Interview Questions

Everyone knows about the linear search algorithm and it's working.Today I will tell you how can you improve your linear search algorithm with some improvement in your code.
Let's first talk about linear search:

Linear search is a basic algorithm where we compare elements one by one with our key element.

here is an Array of 10 elements in which we have to search 33 ..

Loop will start from index 0 = 12 and we compasre it with key 33 and we do comparison till we will not get the key ..

Algorithm:

int key;

for(int I=0;i<length;i++)

if(A[I]==key)

return I;

so here if key will be found at nth index then the total comparison will be O(n)..

here is a catch to improve the time complexity of given problem by adding some extra bit of code.

It will make your linear search algorithm a smart algo..

Smart Linear search 1 :

In above problem we were searching 33 and we find it at index 7.so next time if again search for 33 how much time it will take , 7 right .. yups but using this algorithm you can reduce the search time by 1 unit ..

Algorithm :

int key;

for(int I=0;i<length;i++)

if(A[I]==key) 

swap(A[I] ,A[I-1])

 return I-1;

so  if you use above algorithm in your code it will reduce the running time by 1 unit in each iteration.

It will help you searching those key elements which you searched repeatedly .

Let's analyze it. 

We were searching 33 and it found at index 7 and then we swap the index 7 with index 6 so the 33 now at index 6 .. so if you again search 33 you will get it 1 unit before the ideal Linear search algorithm.

Smart Linear search 2 :

this algorithm reduces the complexity rapidly if you search key value repeatedly . here's the algorithm for doing it.

Algorithm :

int key;

for(int I=0;i<length;i++)

if(A[I]==key) 

swap(A[I] ,A[0])

 return 0;

Time Complexities : 

Standard Linear Search (For repeatedly Search of same Key ) = O(n);

Advanced Linear Search 1 (For repeatedly Search of same Key ) = O(n-1);

Advanced Linear Search 2 (For repeatedly Search of same Key ) = O(1);

Hope this article helped you .. 

C++ Code for Advanced Linear Search :