Searching algorithms are fundamental to computer science which search an elements from a given list. Searching is widely applicable in our daily lives including searching items in retail store website and files in our computer. In this article, we will introduce the concepts behind several searching algorithms, followed by a complete Python code for applying them to a sample unsorted list.
The algorithms are generally classified into two categories, sequential search and interval search. Sequential search is designed to search every elements in the list while interval search is designed to search in sorted list by a certain interval. Interval search is much more efficient than sequential search but it requires list to be sorted before searching.
Bubble sort is applied to sort the list before performing interval search algorithms in our example. A compare function is also developed for applying searching algorithms.
# bubble sort algorithm
# interval search algorithm requires sorted list before searching
def bubblesort(samplelist):
length = len(samplelist)
while True:
no_change_flag = True
for i in range(length-1):
if samplelist[i+1] < samplelist[i]:
samplelist[i], samplelist[i+1] = samplelist[i+1], samplelist[i]
no_change_flag = False
if no_change_flag:
break
return samplelist
# compare two elements and return the minimum element
def codemin(target1, target2):
if target1 > target2: return target2
return target1
Linear search is considered as the most intuitive way to search elements in the list, by looping every element in the list before locating the element.
Example
Sample: [2, 8, 5, 12, 23, 16, 72, 38, 56, 91]
1st Target: 23, 2nd Target: 7
1st Target
1st step: Compare 2, 23 → Not match
2nd step: Compare 8, 23 → Not match
...
5th step: Compare 23, 23 → Match → Return index 4
2nd Target
Return index -1 after iterating the whole list since 7 is not found in the list
def linearsearch(samplelist, target):
idx = -1
for i, i_values in enumerate(samplelist):
if target == i_values:
idx = i
# break the loop once the element is found
break
return idx
print(linearsearch(sample, target1))
# 4
print(linearsearch(sample, target2))
# -1
Linear search is relatively exhaustive since it is required to loop and compare every other element.
Binary search is designed to search a sorted list by repeatedly dividing the search interval in half which does not require to search every element in the list. The value of the search is firstly compared to the element in the middle of the list and then narrow the interval to the lower half if it is smaller than the middle element or to the upper half if it is larger than the middle element. The search continues by halving the list until the search element is found.