What is Linear Search in Data Structure?

July 21, 2018

The study of data structures for facilitating rapid searching is a fascinating subject of both practical and theoretical interest. Sorting and Searching are two fundamental operations in a computer science. Sorting means arranging on data in given order such that increment or decrement. Searching means find out location or find out an element of a given item in a collection of item. Searching element is any type of a numerical data, alphabet, String, character data. Every searching algorithm depends on specific problem, property of data and algorithm complexity. A search algorithm is the step by step procedure used to locate specific data among the collections of data. Searching is considered as the most fundamental procedure in computer science. When the data is to be searched, the difference between a fast application and a slower one lies in the use of proper search algorithms.

Definition of Linear Search

Linear search, also known as sequential search, is a process that checks every element in the list sequentially until the desired element is found. The computational complexity for linear search is O(n), making it generally much less efficient than binary search (O(log n)).

Linear search (sequential search) is the most simple approach to find out, whether the array (or a different data structure) contains some element. The principle of linear search is trivial – iterate over all elements stored in the structure and compare them with the searched one. In the worst case – the last element is equal to the searched one or the structure does not contain the element at all – linear search has to perform n comparisons, hence the asymptotic complexity of the algorithm is O (n).

Linear search is a very basic and simple search algorithm. In Linear search, we search an element or value in a given array by traversing the array from the starting, till the desired element or value is found.

Implementing Linear Search

Linear search algorithm finds given element in a list of elements with O (n) time complexity where n is total number of elements in the list. This search process starts comparing of search element with the first element in the list. If both are matching then results with element found otherwise search element is compared with next element in the list. If both are matched, then the result is “element found”. Otherwise, repeat the same with the next element in the list until search element is compared with last element in the list, if that last element also doesn’t match, then the result is “Element not found in the list”. That means, the search element is compared with element by element in the list.

Linear search is implemented using following steps:

• Step 1:Read the search element from the user
• Step 2:Compare, the search element with the first element in the list.
• Step 3:If both are matching, then display “Given element found!!!” and terminate the function
• Step 4:If both are not matching, then compare search element with the next element in the list.
• Step 5:Repeat steps 3 and 4 until the search element is compared with the last element in the list.
• Step 6:If the last element in the list is also doesn’t match, then display “Element not found!!!” and terminate the function

Algorithm of Linear Search

 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

Example of Linear Search

Consider the following:

Search 7 in give array with 10 elements.

Usage

We use linear search, when we have no information about the ordering of elements in the given structure and when the data structure itself does not support more efficient ways to find an element (for example hashing). If the data structure supports random access and its elements are ordered, we should use more effective algorithms – binary search or interpolation search.

References

[1]Linear Search Algorithm: Sequential Search”, available online at: http://btechsmartclass.com/DS/U4_T1.html

[2] “Linear search”, available online at: http://www.programming-algorithms.net/article/40168/Linear-search

[3] Morrice Joseph and Palak Keshwani, “Comparison between Linear Search And Binary Search Algorithms”, IJARIIT, 2018

[4] Kamlesh Kumar Pandey and Narendra Pradhan, “A Comparison and Selection on Basic Type of Searching Algorithm in Data Structure”, International Journal of Computer Science and Mobile Computing, IJCSMC, Vol. 3, Issue. 7, July 2014, pg.751 – 758

[5] “Data Structure and Algorithms Linear Search”, available online at: https://www.tutorialspoint.com/data_structures_algorithms/linear_search_algorithm.htm

$${}$$