Linear search: Difference between revisions
From Coderwiki
More actions
new |
link to Collection |
||
| Line 1: | Line 1: | ||
A '''linear search''' is a [[search algorithm]] which simply steps through each [[Array element|element]] of an [[array]] or [[ | A '''linear search''' is a [[search algorithm]] which simply steps through each [[Array element|element]] of an [[array]], [[list]] or other [[collection]] and checks if it matches the target [[value]]. | ||
== Advantages of a linear search == | == Advantages of a linear search == | ||
| Line 5: | Line 5: | ||
* [[Performance|Faster]] than a [[binary search]] on '''very''' small datasets | * [[Performance|Faster]] than a [[binary search]] on '''very''' small datasets | ||
* Very easy to implement | * Very easy to implement | ||
* The [[ | * The [[collection]] does '''not''' need to be [[Sort algorithm|in order]] | ||
== Disadvantages of a linear search == | == Disadvantages of a linear search == | ||
| Line 14: | Line 14: | ||
This will print the [[Array index|index]] of the '''first instance''' of the number <code>9</code> in the [[list]]. | This will print the [[Array index|index]] of the '''first instance''' of the number <code>9</code> in the [[list]]. | ||
It would make more sense to use Python's <code>enumerate</code> method here, but we don't use it as it is not necessarily found in other languages (and this wiki aims to be as generic as possible).<syntaxhighlight lang="python" line="1"> | ''It would make more sense to use Python's <code>enumerate</code> method here, but we don't use it as it is not necessarily found in other languages (and this wiki aims to be as generic as possible).''<syntaxhighlight lang="python" line="1"> | ||
data = [3, 4, 7, 9, 1, 2, 9, 12] | data = [3, 4, 7, 9, 1, 2, 9, 12] | ||
target = 9 | target = 9 | ||
Latest revision as of 07:56, 13 August 2025
A linear search is a search algorithm which simply steps through each element of an array, list or other collection and checks if it matches the target value.
Advantages of a linear search
edit edit source- Faster than a binary search on very small datasets
- Very easy to implement
- The collection does not need to be in order
Disadvantages of a linear search
edit edit source- Almost always slower than a binary search
Example: linear search in Python
edit edit sourceThis will print the index of the first instance of the number 9 in the list.
It would make more sense to use Python's enumerate method here, but we don't use it as it is not necessarily found in other languages (and this wiki aims to be as generic as possible).
data = [3, 4, 7, 9, 1, 2, 9, 12]
target = 9
for i in range(len(data)): # loop over indices of data list
element = data[i] # get the element at the current index
if element == target: # check if element matches target
print(i) # print index of first occurance
break # stop after first instance