๐Ÿ“š

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.3kย โ€ขย 69ย 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?

Join us on Discord
Thousands of students are studying with us for the AP Computer Science Principles exam.
join now
Hours Logo
Studying with Hours = the ultimate focus mode
Start a free study session
๐Ÿ” Are you ready for college apps?
Take this quiz and find out!
Start Quiz
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
โœ๏ธBlogs
๐Ÿ“Exam Prep
Join us on Discord
Thousands of students are studying with us for the AP Computer Science Principles exam.
join now
๐Ÿ’ช๐Ÿฝ Are you ready for the AP CSP exam?
Take this quiz for a progress check on what youโ€™ve learned this year and get a personalized study plan to grab that 5!
START QUIZ
๐Ÿ“ฑ 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.