Complexity of common search algorithms
Searching is a technique of selecting a certain portion of a dataset based on a certain set criterion. We use search algorithms in our day-to-day life when we search for something on the web that meets a certain word or phrase of our choice. Hence, to be able to search a data structure for required data is crucial in developing different kinds of applications.
In this section, we will discuss two search algorithms that are used in Python:
- Linear search algorithm
- Binary search algorithm
Linear search algorithm
This is the simplest kind of search algorithm to a sequential search problem. It simply checks the items in sequence until the desired item is found. This kind of search algorithm has already been illustrated using Example 2 (where we calculate the execution time of an algorithm). Let's look at a similar example to reinforce it, but this time we will write a function to carry out the linear search.
What...
