πŸ“š

All Subjects

Β >Β 

⌨️ 

AP Comp Sci P

Β >Β 

πŸ“±

Big Idea 3: Algorithms and Programming

Binary Search

2 min readβ€’november 16, 2020

minnachow

Minna Chow


AP Computer Science Principles ⌨️

BookmarkedΒ 2.9kΒ β€’Β 79Β resources
See Units

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.

Traversing a 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.
1, 1, 2, 3, 3, 4, 5, 7, 9, 11, 12
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.
5, 7, 9, 11, 12
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.)

Was this guide helpful?

Fiveable logo
Join Fiveable for free
Create a free account to bookmark content and compete in trivia
Hours Logo
Studying with Hours = the ultimate focus mode
Start a free study session
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
πŸ“± Stressed or struggling and need to talk to someone?
Talk to a trained counselor for free. It's 100% anonymous.
Text FIVEABLE to 741741 to get started.
Β© 2021 Fiveable, Inc.