Searching-
- Searching is a process of finding a particular element among several given elements.
- The search is successful if the required element is found.
- Otherwise, the search is unsuccessful.
Searching Algorithms-
Searching Algorithms are a family of algorithms used for the purpose of searching.
The searching of an element in the given array may be carried out in the following two ways-
- Linear Search
- Binary Search
Linear Search-
- Linear Search is the simplest searching algorithm.
- It traverses the array sequentially to locate the required element.
- It searches for an element by comparing it with each element of the array one by one.
- So, it is also called as Sequential Search.
Linear Search Algorithm is applied when-
- No information is given about the array.
- The given array is unsorted or the elements are unordered.
- The list of data items is smaller.
Linear Search Algorithm-
Consider-
- There is a linear array ‘a’ of size ‘n’.
- Linear search algorithm is being used to search an element ‘item’ in this linear array.
- If search ends in success, it sets loc to the index of the element otherwise it sets loc to -1.
Time Complexity Analysis-
Linear Search time complexity analysis is done below-
Best case-
In the best possible case,
- The element being searched may be found at the first position.
- In this case, the search terminates in success with just one comparison.
- Thus in best case, linear search algorithm takes O(1) operations.
Worst Case-
In the worst possible case,
- The element being searched may be present at the last position or not present in the array at all.
- In the former case, the search terminates in success with n comparisons.
- In the later case, the search terminates in failure with n comparisons.
- Thus in worst case, linear search algorithm takes O(n) operations.
