Linear Search
- Linear search is a simple searching algorithm.
- In this search, a sequential search is done over all items one by one from the starting to the ending of the array.
- Every item is checked and if a match is found then that particular item is selected and the index is returned, otherwise the search continues till the end of the data collection.
Example:
14 |
28 |
34 |
36 |
48 |
60 |
72 |
80 |
0 1 2 3 4 5 6 7
Search for an item= 48
- Searching will start from starting position of array i.e, 14 and keep searching for the element 48 till it is not found.
- Element 48 is present in the index no.= 4
Algorithm:
Linear Search ( Array A, Value x)
Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit
Note:
- Linear search is also known as “Sequential search”.
- If in a array n-elements are present then the worst case time complexity can be n-times due to sequential search and we can also achieve best case time complexity if the finding element is present at the beginning.
Application:
- Linear search is usually very simple to implement, and is practical when the list has only a few elements, or when performing a single search in an unordered list.
Drawbacks:
- We know Linear search is very easy due to it’s so dam simple technique to implement, but it is not used practically because binary search is a lot faster than linear search.
Real life example:
finding a book in library