π

All Subjects

Β >Β

β¨οΈΒAP Comp Sci P

Β >Β

π±Big Idea 3: Algorithms and Programming

2 min readβ’november 16, 2020

Minna Chow

The most common way of traversing a list is to go through each item in order, one at a time.

This is also the most basic way to search through a list. This search method is called a linear or **sequential search** algorithm, and it checks each value of a list in order until the result is found.

However, this isn't the only way you can search through a list. You can also look through a list using a **binary search. **

The binary search algorithm starts in the middle of a *sorted* data set and eliminates half of the data based on what it's looking for. It then repeats the process until the desired value is found or until the algorithm has exhausted all the values in the list.

For example, let's say you had a list that looked like this:

1, 1, 2, 3, 3, 4, 5, 7, 9, 11, 12

and you wanted to find where **12** was.

If you were doing a binary search, you would divide the list in half and look at the value there, which would be 4.

1, 1, 2, 3, 3, **4**, 5, 7, 9, 11, 12

12 is greater than 4, so the program knows to disregard everything before and including that value.

The program would then divide the list into half again...

5, 7, **9**, 11, 12

and look at the value 9. 9 is less than 12, so the program would eliminate everything before and including that value.

This process would go on until the program either found 12 or went through all the values in the list.

Data must first be* sorted* in order to use a binary search method. However, when used on sorted data, a binary search is often more efficient than a sequential search because it eliminates half the data with each round of splitting. This means that it doesn't have to evaluate many of the results, saving time that the program would usually spend going down the list in a sequential sort. Due to this, the binary search method is commonly used in modern programs.

π Check out this video explaining binary searches, as well as ways they can be written out. To see a binary search algorithm written in Python, go here. (Don't worry, you won't need to know how the algorithm works for the test.)

Join Fiveable for free

Create a free account to bookmark content and compete in trivia

Browse Study Guides By Unit

πΉBig Idea 1: Creative Development

βοΈBig Idea 2: Data

π±Big Idea 3: Algorithms and Programming

π₯Big Idea 4: Computer Systems and Networks

β¨οΈBig Idea 5: Impact of Computing

βοΈFrequently Asked Questions

πExam Prep