Problem: Given an array arr[] of n elements, write a function to search a given element x in arr[].
A simple approach is to do linear search, i.e
- Start from the leftmost element of arr[] and one by one compare x with each element of arr[]
- If x matches with an element, return the index.
- If x doesn’t match with any of elements, return -1.
Example:
C and C++
[pastacode lang=”c” manual=”%2F%2F%20Linearly%20search%20x%20in%20arr%5B%5D.%20%20If%20x%20is%20present%20then%20return%20its%20%0A%2F%2F%20location%2C%20%20otherwise%20return%20-1%0Aint%20search(int%20arr%5B%5D%2C%20int%20n%2C%20int%20x)%0A%7B%0A%20%20%20%20int%20i%3B%0A%20%20%20%20for%20(i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20if%20(arr%5Bi%5D%20%3D%3D%20x)%0A%20%20%20%20%20%20%20%20%20return%20i%3B%0A%20%20%20%20return%20-1%3B%0A%7D” message=”C and C++” highlight=”” provider=”manual”/] [ad type=”banner”]Python
[pastacode lang=”python” manual=”%23%20Searching%20an%20element%20in%20a%20list%2Farray%20in%20python%0A%23%20can%20be%20simply%20done%20using%20’in’%20operator%0A%23%20Example%3A%0A%23%20if%20x%20in%20arr%3A%0A%23%20%20%20print%20arr.index(x)%0A%20%0A%23%20If%20you%20want%20to%20implement%20Linear%20Search%20in%20python%0A%20%0A%23%20Linearly%20search%20x%20in%20arr%5B%5D%0A%23%20If%20x%20is%20present%20then%20return%20its%20location%0A%23%20else%20return%20-1%0A%20%0Adef%20search(arr%2C%20x)%3A%0A%20%0A%20%20%20%20for%20i%20in%20range(len(arr))%3A%0A%20%0A%20%20%20%20%20%20%20%20if%20arr%5Bi%5D%20%3D%3D%20x%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20i%0A%20%0A%20%20%20%20return%20-1″ message=”Python” highlight=”” provider=”manual”/]Java
[pastacode lang=”java” manual=”class%20LinearSearch%0A%7B%0A%20%20%20%20%2F%2F%20This%20function%20returns%20index%20of%20element%20x%20in%20arr%5B%5D%0A%20%20%20%20static%20int%20search(int%20arr%5B%5D%2C%20int%20n%2C%20int%20x)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Return%20the%20index%20of%20the%20element%20if%20the%20element%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20is%20found%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(arr%5Bi%5D%20%3D%3D%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20i%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20return%20-1%20if%20the%20element%20is%20not%20found%0A%20%20%20%20%20%20%20%20return%20-1%3B%0A%20%20%20%20%7D%0A%7D%20″ message=”Java” highlight=”” provider=”manual”/]The time complexity of above algorithm is O(n).
Linear search is rarely used practically because other search algorithms such as the binary search algorithm and hash tables allow significantly faster searching comparison to Linear search.
[ad type=”banner”]