Linear Search

This algorithm is used for Strings and Lists often.
index()
andfind()
are linear searchesin
andnot in
membership for strings and lists are linear searches
Algorithm Classification
Big-O: O(n) hence the name โLinearโ Search โฆ happens when the target is not found -or- target is the last value
Big-Omega: O(1) very first item is the target
Big-Theta: O(n/2) which simplifies to O(n) โฆ target is found somewhere in the middle
Linear Search Algorithm:
# Let L be a list of items; i be the index, and N be the number of items
# Let T be a Target
1 Set i to 0
2 If L at i == Target, then return i
3 Else increase i by 1 and repeat back to Line 2
4 If i > N, and target has not been found, then return -1
Note on using a while loop
#Method 2
def linSearch(array, target):
ctr = 0
while ctr < len(array):
if array[ctr] == target:
return ctr
ctr += 1
else:
return -1
Last updated