Binary search facts for kids

Imagine you're looking for a specific card in a perfectly sorted deck. Binary search helps you find it super fast!

In computer science, binary search is a clever way to find something in a list that is already sorted. Think of it like looking up a word in a dictionary. You don't start from the very beginning! This method is much faster than a linear search, which checks every single item one by one. But remember, binary search only works if your list is sorted, like numbers from smallest to largest, or words in alphabetical order.

The idea behind binary search is simple: you keep cutting the list in half. You look at the middle item. If it's what you're looking for, great! If not, you decide if your item is in the first half or the second half. Then, you repeat the process on that smaller half. You keep doing this until you find your item or realize it's not there.

How Binary Search Works

First, you need a sorted list and the item you want to find (let's call it the "target"). The algorithm then looks at the item exactly in the middle of your list.

• If the middle item is your target: Hooray! You found it. The algorithm tells you where it is in the list.
• If the middle item is bigger than your target: This means your target must be in the first half of the list (the smaller numbers). So, the algorithm ignores the second half and focuses only on the first half.
• If the middle item is smaller than your target: This means your target must be in the second half of the list (the larger numbers). The algorithm then ignores the first half and focuses on the second half.

This process repeats. Each time, the list you are searching gets cut in half. This makes binary search super quick, especially for very long lists!

To find the middle item, you can use a simple math trick: Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): Middle\ item\ position = \frac{Position\ of\ Smallest\ item + Position\ of\ Biggest\ item}{2} You just round this number down to the nearest whole number.

An Example in Action

Let's say you want to find the number 84 in this list of 9 sorted numbers:

Here's how binary search finds 84:

In just 3 steps, the algorithm found 84 at position 7! If the number wasn't in the list, the algorithm would keep searching until there were no more items left to check. Then it would tell you it couldn't find it.

How It's Built (Implementation)

When programmers build a binary search, they often use something called a while loop. This loop keeps running as long as there are still items to check in the list. Inside the loop, the program checks if the middle item is the one it's looking for, or if it needs to search the lower or upper half of the list.

This makes sure the search continues until the item is found or all possibilities are checked.

Related Pages

• Linear search
• Breadth-first search
• Depth-first search

See also

In Spanish: Búsqueda binaria para niños