Learn: Binary Search - How It Works

Welcome!Welcome back! You've already learned about how linear search works and how to trace it through a data set. Today, we'll build on that understanding and explore binary search, a faster way to find data in a sorted list.Get ready for an interactive and fun session!

What is Binary Search?Binary search is an algorithm used to efficiently find a target value in a sorted list. Instead of checking one item at a time like linear search, binary search splits the list in half and focuses on the part where the target could be. This makes it much faster!

How Does Binary Search Work?Binary search works by dividing the list into halves repeatedly. It checks the middle item of the list. If the target value matches, the search stops. If not, it decides whether the target is in the lower half or upper half, then repeats the process until the value is found or the list is empty.

Steps of Binary SearchHere are the steps for binary search:Start with the entire sorted list.Find the middle item.Compare the middle item to the target value.If it matches, stop. If not, decide whether the target is in the lower or upper half.Repeat the process with the smaller half until the target is found or the list is empty.

Why is Binary Search Faster?In linear search, you might have to check every item in the list one-by-one, which takes a long time for large lists. Binary search halves the search space with every step, making it much faster. For example, a list with 1,000 items can be searched in about 10 steps!

Tracing Binary SearchLet's go through an example. Imagine you have a sorted list: [1, 3, 5, 7, 9, 11, 13, 15]. You want to find 9. First, check the middle element (7). Is it 9? No. Is 9 larger or smaller than 7? Larger. So now only the upper half of the list needs to be checked. Repeat the process!

Review Time!Great work! You've learned all about binary search, how it works, why it's faster, and how to trace it step-by-step. Let's test your understanding with a few final questions.

Congratulations!You've mastered binary search. Keep practising tracing it on different data sets to build confidence. Well done!