1. Linear Search and Binary Search
Now, we will will focus on searching algorithms, like linear search, binary search, depth first search, and breadth first search. We will also study binary search trees and how to search within them.
2. Searching algorithms
Searching for an element in a data structure is an essential operation,
and there are several ways to do it. In this video, we will explore two
algorithms that search for an element within a collection of elements:
linear search
and binary search.
3. Linear search
Linear search tries to search for a value by looping through each element of the list.
If the element is found,
the algorithm stops
and returns the result.
Otherwise,
the algorithm continues.
4. Linear search
Let's implement this algorithm.
We iterate over the elements on the list
and check if the element located at the index we are considering is equal to the search value. If it is,
we return True. If it is not, the for loop will continue. If the loop finishes without returning True,
we will return False because we won't have found the search value.
We can execute this algorithm as shown.
5. Linear search - complexity
Linear search has a complexity of O of n. Let's improve this complexity with binary search.
6. Binary search
Binary search only applies to ordered lists.
Suppose we have this ordered list and want to determine
whether it contains the number 15.
7. Binary search
We can define a variable called first and set it to the first position of the list
8. Binary search
and another variable called last set to the last position.
While we have elements to iterate over,
9. Binary search
we will set the middle variable to the middle of the list
10. Binary search
and compare search_value with the item in the middle of the list. If they are equal,
we return True because we found it.
If search_value is less,
11. Binary search
we move last to the value of middle minus one, so we can continue looking at the first half of the list in the next iteration. However,
12. Binary search
if the search value is greater than the element in the middle, as in this example,
13. Binary search
we move first to the value of middle plus one so that we can continue looking at the second half of the list. To finish this example, we will iterate this way again.
14. Binary search
We move middle
15. Binary search
and compare it with search_value. As search_value is less than middle,
16. Binary search
we move last.
17. Binary search
We move middle again
18. Binary search
and compare it with search_value. As they are equal,
19. Binary search
we return True and finish the execution. If we hadn't found the search number,
we would have returned False.
20. Binary search - complexity
The complexity of binary search is O of log n, which is
much better than the linear search complexity, especially when the size of the lists is big.
21. Let's practice!
Let's practice!