Unit 2
Program for Linear Search
Aim:
• To implement Linear search algorithm
Theory:
• Linear search is also called as sequential search algorithm.
• It is the simplest searching algorithm.
• In Linear search, we simply traverse the list completely and match
each element of the list with the item whose location is to be found.
• If the match is found, then the location of the item is returned;
otherwise, the algorithm returns NULL.
• It is widely used to search an element from the unordered list,
• i.e., the list in which items are not sorted.
• The worst-case time complexity of linear search is O(n).
Working of Linear search
• To understand the working of linear search algorithm we will take an
unsorted array.
• Let the elements of array are –
• If the element to be searched is K = 41
• start from the first element and compare K with each element of the array.
• The value of K, i.e., 41, is not matched with the first element of the array. So,
move to the next element. And follow the same process until the respective
element is found.
• Now, the element to be searched is found.
• So algorithm will return the index of the element matched
Time Complexity
• Best Case Complexity –
• In Linear search, best case occurs when the element we are finding is
at the first position of the array.
• The best-case time complexity of linear search is O(1).
• Worst Case Complexity - In Linear search, the worst case occurs when
the element we are looking is present at the end of the array.
• The worst-case in linear search could be when the target element is
not present in the given array, and we have to traverse the entire
array.
• The worst-case time complexity of linear search is O(n).
Space Complexity
• In Linear Search, we are creating a boolean variable to store if the
element to be searched is present or not.
• The variable is initialized to false and if the element is found, the
variable is set to true.
• This variable can be used in other processes or returned by the
function.
• As the amount of extra data in Linear Search is fixed, the Space
Complexity is O(1).
• Therefore, Space Complexity of Linear Search is O(1).
Procedure:
simple approach to implement a linear search is
• Step1 : Begin with the leftmost element of arr[] and one by one
compare x with each element.
• Step 2:If x matches with an element then return the index.
• Step 3: If x does not match with any of the elements then return -1.
Program
Output
