Linear search
Linear search is an algorithm which is also known under the name sequential search. He is the simplest search algorithm at all.
The task is to find an item in a list or an array with n elements. You go to through the list item by item, until you find it. The search effort grows linearly with the number of elements in the list.
If the data is randomly distributed, then comparison operations are needed on average N / 2. In the best case is equal to the first element of the list that which you are looking, at worst it is the last.
If the number of elements in a list is small, it is often the most efficient method.
The more efficient binary search can be used only with ordered lists.
For unordered lists exist with lazy yet Select a randomized algorithm that can find the x - th element of a list with respect to an order faster than in linear time with relatively high probability.
Implemented in pseudo-code
STARTING Linear Search INPUT: (S) uchschlüssel, (A) rray VARIABLE: N = number of elements in the array 'A' VARIABLE: Find Success = false VARIABLE: i = 0 FOR i TO N OR Search Success When A [i] = S THEN Successful search = true IF Successful search = true THEN ISSUE: i Unsuccessful search: ELSE OUTPUT END Example implementation in Ruby
Def Lineare_suche ( data array, value ) for i in data array return true if i == value; end return false end Example implementation in Objective CAML
Let rec linsuche = function ([], a) - > false | (X :: t, a) - > if x = a then true else linsuche (t, a);; Sample implementation in Java
The example returns the value -1 if the element searched for is not in the array " data" available. Otherwise, it returns the position of the element.
Public static int linear search ( final int wanted, final int [ ] data) { for (int i = 0; i < daten.length; i ) { if ( data [ i] == sought ) { return i; } } return -1; } Example implementation in Python
Finds all the search key in the list.
Def lineare_suche ( list, searched ): idxs = [] for index, element in enumerate ( list): if element == looking for: idxs.append (index) return idxs # Or lineare_suche = lambda l, g: [i for i, e in enumerate ( l ) if g == e] Finds first occurrence of the search key in a list.
Def lineare_suche ( list, searched ): for index, element in enumerate ( list): if element == looking for: return index # And there are already lineare_suche = lambda l, g: l.index ( g ) if g in l else None see also
- Search algorithm