Studyfin
✨ Sign up free
Hey there! Today we are going to explore how computers find information in a flash using search algorithms.
When we want a computer to find an item in a list, we use a search algorithm. A simple way is linear search, where the computer checks every single item one by one from start to finish.
Checking items one by one can take a long time for big lists. To make this faster, we analyze the benefits of using iteration, which is repeating a set of instructions in a loop to automate the search.
If our list is sorted, we can use a much faster method called binary search. This algorithm repeatedly splits the list in half, discarding the half that cannot contain our target value.
By analyzing the benefits of iteration, we see it allows us to write a single loop that handles lists of any size. Instead of writing millions of lines of code, iteration lets a few lines repeat until the item is found.
Let's analyze how many steps a linear search and a binary search would take to find the number 11 in this sorted list: [2, 5, 8, 11, 14, 17, 20].
- Step 1: Identify the target value. Our target is 11.
- Step 2: Trace the linear search. It starts at index 0 and checks each number: 2 (no), 5 (no), 8 (no), 11 (yes!). This took 4 steps.
- Step 3: Trace the binary search. First, find the middle element of the list. The middle element of [2, 5, 8, 11, 14, 17, 20] is 11.
- Step 4: Compare the middle element to our target. Since the middle element is 11, we found our target in just 1 step!
- Step 5: Compare the efficiency. In this case, binary search found the target in 1 step, while linear search took 4 steps. Iterating by halving is much faster!
