Linear search

Linear search

In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a list of data for a particular value.

It operates by checking every element of a list one at a time in sequence until a match is found. Linear search runs in O(n). If the data are distributed randomly, the expected number of comparisons that will be necessary is:

egin{cases} n, & k = 0 \ frac{n + 1}{k + 1}, & 1 le k le nend{cases}

where n is the number of elements in the list and k is the number of times that the value being searched for appears in the list. The best case is that the value is equal to the first element tested, in which case only 1 comparison is needed. The worst case is that the value is not in the list (or it appears only once at the end of the list), in which case n comparisons are needed

The simplicity of the linear search means that if just a few elements are to be searched it is less trouble than more complex methods that require preparation such as sorting the list to be searched or more complex data structures, especially when entries may be subject to frequent revision. Another possibility is when certain values are much more likely to be searched for than others and it can be arranged that such values will be amongst the first considered in the list.

The following pseudocode describes the linear search technique.

For each item in the list: Check to see if the item you're looking for matches the item in the list. If it matches. Return the location where you found it (the index). If it does not match. Continue searching until you reach the end of the list. If we get here, we know the item does not exist in the list. Return -1.

In computer implementations, it is usual to search the list in order, from element 1 to N (or 0 to N - 1, if array indexing starts with zero instead of one) but a slight gain is possible by the reverse order. Suppose an array "A" having elements 1 to N is to be searched for a value "x" and if it is not found, the result is to be zero. for i:=N:1:-1 do %Search from N down to 1. (The step is -1) if A [i] = x then QuitLoop i; next i; Return(i); %Or otherwise employ the value.Implementations of the loop must compare the index value "i" to the final value to decide whether to continue or terminate the loop. If this final value is some variable such "N" then a subtraction "(i - N)" must be done each time, but in going down from "N" the loop termination condition is for a constant, and moreover a special constant. In this case, zero. Most computer hardware allows the sign to be tested, especially the sign of a value in a register, and so execution would be faster. In the case where the loop was for arrays indexed from zero, the loop would be "for i:=N - 1:0:-1 do" and the test on the index variable would be for it negative, not zero.

The pseudocode as written relies on the value of the index variable being available when the for-loop's iteration is exhausted, as being the value it had when the loop condition failed, or a 'QuitLoop' was executed. Some compilers take the position that on exit from a for-loop no such value is defined, in which case it would be necessary to copy the index variable's value to a reporting variable before exiting the loop, or to use another control structure such as a "while" loop, or else explicit code with "go to" statements in pursuit of the fastest-possible execution.

The following code example for the Java programming language is a simple implementation of a linear search.

public int linearSearch(int a [] , int valueToFind) { //a [] is an array of integers to search. //valueToFind is the number that will be found. //The function returns the position of the value if found. //The function returns -1 if valueToFind was not found. for (int i=0; iThe List module in the OCaml standard library defines a function called "mem" that returns true if the given element is in the given list or false if not. This function could be defined as:

let rec mem x = function [] -> false
h :: t -> h=x || mem x t

Mathematica's unusually powerful pattern matching allows linear search to be implemented by a pattern match:

Mem [x_, {___, x_, ___}] := TrueMem [_, _] := False

Linear search can be used to search an unordered list. Unordered lists are easy to implement as arrays or linked lists, and insertion and deletion can be done in constant time. The simplicity of a linearly searched unordered list means it is often the first method chosen when implementing lists which change in size while an application runs. If this later proves to be a bottleneck it can be replaced with a more complicated scheme.

The average performance of linear search can be improved by using it on an ordered list. In the case of no matching element, the search can terminate at the first element which is greater (lesser) than the unmatched target element, rather than examining the entire list.

An ordered list is a more efficient data structure in general for searching than an unordered list. A binary search can often be used with an ordered list instead of a linear search. It is more difficult to implement correctly but examines much less than the entire list to determine presence or absence of an element.

As the number of elements in the list grows or as the number of searches increases, the more desirable something other than a linear search becomes. Another common method is to build up a hash table and then do hash lookups.

ee also

*Binary search
*Ternary search
*Hash table

References

* Donald Knuth. "The Art of Computer Programming", Volume 3: "Sorting and Searching", Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.1: Sequential Searching, pp.396–408.

External links

* [http://www.paked.net/subject_pages/computer_science/prog5.htm C++ Program - Linear Search ]
* [http://www15.brinkster.com/selvamselvam/linearsearch.html C Program - Linear Search ]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • linear search — nuoseklioji paieška statusas T sritis informatika apibrėžtis ↑Paieška, kai peržiūrimi visi duomenys paeiliui. Paieškos srities elementai analizuojami iš eilės pagal loginę arba fizinę seką. Tai paprasčiausias ir lėčiausias paieškos metodas,… …   Enciklopedinis kompiuterijos žodynas

  • Search algorithm — In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. Most of the algorithms studied by computer… …   Wikipedia

  • Search data structure — In computer science, a search data structure is any data structure that allows the efficient retrieval of specific items from a set of items, such as a specific record from a database. The simplest, most general, and least efficient search… …   Wikipedia

  • Linear programming — (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.… …   Wikipedia

  • Linear partial information — (LPI) is a method of making decisions based on insufficient or fuzzy information. LPI was introduced in 1970 by Polish Swiss mathematician Edward Kofler (1911 2007) to simplify decision processes. Comparing to other methods the LPI fuzziness is… …   Wikipedia

  • Search-based software engineering — (SBSE) is an approach to apply metaheuristic search techniques like genetic algorithms, simulated annealing and tabu search to software engineering problems. It is inspired by the observation that many activities in software engineering can be… …   Wikipedia

  • Linear-motion bearing — A linear motion bearing or slide is a bearing designed to provide free motion in one dimension. There are many different types of linear motion bearings and this family of products is generally broken down into two sub categories: rolling element …   Wikipedia

  • Linear Pottery culture — LBK redirects here. For other uses, see LBK (disambiguation). Not to be confused with Linear B. Map of European Neolithic at the apogee of Danubian expansion, c. 4500–4000 BC …   Wikipedia

  • Linear programming relaxation — In mathematics, the linear programming relaxation of a 0 1 integer program is the problem that arises by replacing the constraint that each variable must be 0 or 1 by a weaker constraint, that each variable belong to the interval [0,1] .That is,… …   Wikipedia

  • Linear B — Infobox Writing system name=Linear B type=Syllabary typedesc=with additional Logograms time=Late Bronze Age status=Extinct languages=Mycenaean Greek fam1= Linear A sisters=Cypro Minoan syllabary unicode=… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”