Get startedGet started for free

Linear Search and Binary Search

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!