The ability to search for some data is an important aspect of computer science. Search algorithms are used to look for a particular item in a data set.
Algorithms return a boolean result (true or false) to a search query. They can also be modified to give the relative position of the found value.
For this article, the algorithms will concentrate on determining whether a value exists.
Linear Search Algorithms
Linear search is also known as sequential search. In this type of search, each value in a list is visited one by one in an orderly way while checking if the desired value exists.
The algorithm checks value by value until it finds the value you are looking for or runs out of values to search. When it runs out of values to search, that means your search query doesn't exist in the list.
A sequential search algorithm takes in a list of values and the desired item in the list as its parameters. The return result is initialized as False and will change to True when the desired value is found.
See the Python implementation below as an example:
def linearSearch(mylist, item):
found = False
index = 0
while index < len(mylist) and not found:
if mylist[index] == item:
found = True
else:
index = index+1
return found
Algorithm Analysis
The best-case scenario occurs when the desired item is the first one on the list. The worst case occurs when the desired item is the last on the list (the nth item). Therefore, the time complexity for linear search is O(n).
The average case scenario in the above algorithm is n/2.
Modified Linear Search
It's important to know that the algorithm used assumes that a random list of items is provided to it. That is, the list items are in no particular order.
Suppose the items were in a particular order, say from smallest to largest. It would be possible to achieve some advantage in computation.
Take an example of looking for 19 in the given list: [2, 5, 6, 11, 15, 18, 23, 27, 34]. After reaching 23, it would become clear that the item being looked for doesn't exist in the list. Therefore, it would no longer be important to continue searching the rest of the list items.
Binary Search Algorithms
You have seen how an ordered list can reduce the computation needed. Binary search algorithm takes even more advantage of this efficiency that having an ordered list introduces.
The algorithm begins by taking a middle value of an ordered list and checking if it's the desired value. If it's not, then the value is checked whether it's less or greater than the desired value.
If it's less, then there's no need to check the lower half of the list. Otherwise, if it's greater, then it moves on to the upper half of the list.
Regardless of whichever sublist (left or right) is chosen, the middle value will again be determined. The value is again checked if it's the required value. If it's not, it's checked whether it's less or greater than the requested value.
This process is repeated until a value is found if it's there.
The Python implementation below is for the binary search algorithm.
def binarySearch(mylist, item):
low = 0
high = len(mylist) - 1
found = False
while low <= high and not found: mid = (low + high) // 2
if mylist[mid] == item:found = True
elif item < mylist[mid]:high = mid - 1
else:low = mid + 1
return found
Algorithm Analysis
The best-case scenario occurs when the desired item is found to be the middle item. The worst-case scenario is not as straightforward though. Follow the analysis below:
After the first comparison, n/2 items will be left. After the second, n/4 items will be left. After the third, n/8.
Notice that the number of items keeps on halving until they reach n/2i where i is the number of comparisons. After all the splitting, we end up with only 1 item.
This implies:
n/2i=1 Therefore, binary search is O(log n).
Moving on To Sorting
In binary search, we considered a case where the given array was already ordered. But suppose you had an unordered dataset and you wanted to perform binary search on it. What would you do?
The answer is simple: sort it. There are a number of sorting techniques in computer science that have been well researched. One of these techniques you can begin studying is the selection sort algorithm, while we've got plenty of guides related to other areas too.