Lecture notes · Programming in Python · Lecture 6

Bisection Search

MIT 6.100L Intro to CS and Programming using Python, lecture 6, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part reviews why simple guessing is slow, shows why approximation needs a small margin of error, and sets up bisection search as a faster method.

Key ideas

Today's lesson introduces bisection search, a faster algorithm for approximating answers like square roots. It is meant for certain types of problems only. 0:11
Computers store floating point numbers with tiny rounding, so we cannot ask whether a guess is exactly equal to the target. Instead, we allow a small margin called epsilon, meaning the guess only has to be within plus or minus epsilon. 2:24
The approximation loop could run forever, because a guess can jump from just short of the margin to just past it and never land inside. A sanity check fixes this by stopping once guesses become too large to be reasonable. 4:14
Making the steps smaller improves accuracy but costs time. Dividing the step size by 10 made the program make about 10 times as many guesses, so it took far longer. 8:12
Because waiting that long for a simple square root is unreasonable, the lecture points toward bisection search as a much faster approach. 8:56

Words to know

epsilon: A small wiggle-room number. An answer counts as close enough if it is within plus or minus epsilon of the target.
floating point number: A number with a decimal point, such as 0.1. Computers store these with tiny rounding, so they are not always exact.
infinite loop: A loop that never stops because its stopping condition is never met.
guess and check: A method that tries possible answers one by one until it finds one that works. It is slow when there are many possible answers.

Example

Ana's book challenge asks you to find a $100 bill somewhere in a 448-page book in eight or fewer guesses. Checking pages one at a time could take hundreds of tries, so the lecture shows why a smarter way of guessing is needed.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

Bisection search is a fast way to find an answer in an ordered list by guessing the middle and throwing away the half that cannot hold the answer.

Key ideas

When you get a hint like too high or too low, guessing the halfway point lets you throw away half of what is left to search. 13:51
You keep track of a low end and a high end, which form an interval. The answer must lie somewhere inside that interval, and each guess shrinks it. 14:12
Each step repeats the same process on a smaller version of the problem. A computer does this with a loop. 15:41
Cutting the search in half each time is called logarithmic growth. Checking one item at a time is called linear growth, and it is much slower on big problems. 16:49
With bisection search, doubling the size of the search space only adds about one extra guess. With one-at-a-time checking, doubling the size roughly doubles the number of guesses. 17:34

Words to know

bisection search: A method that finds an answer in an ordered list by checking the middle, then keeping only the half that could contain the answer, and repeating.
interval: The range between a low end and a high end where the answer must be. In the book example, the interval started as pages 1 to 448.
logarithmic growth: When the number of steps grows very slowly as the problem gets bigger, because the search space is cut in half at each stage.
linear growth: When the number of steps grows in step with the size of the problem, such as checking one page at a time.

Example

Imagine finding one person in a class lined up alphabetically by last name. You ask the person in the middle for their last name, then ignore the half of the line that cannot contain your person. You repeat this until only one person is left, and that person is the one you want or is not there.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part explains bisection search, a faster way to find a square root by repeatedly guessing the middle of a range and cutting the range in half.

Key ideas

Bisection search starts with a guess at the halfway point of the range, instead of creeping up from 0 one small step at a time. 20:00
You square the guess and compare it to x. If the square is too big, you throw away everything above the guess. If it is too small, you throw away everything below it. 20:19
You repeat the same steps with each new midpoint, so the range of values left to search is cut in half at each guess. 22:07
Bisection search only works when two things are true: the values are in some order, and the feedback tells you whether your guess was too high or too low. 22:29
Bisection search fails when the feedback only says correct or not, and it can run forever when the target is a number like pi that never ends. 24:41

Words to know

bisection search: A way of finding an answer by guessing the middle of a range, then keeping only the half that could hold the answer, and repeating.
midpoint: The point exactly halfway between two numbers. The lesson uses the average of low and high, which is (high + low) divided by 2.
epsilon: A tiny allowed margin of error. Being within plus or minus epsilon means close enough to count as the answer.
feedback: The clue you get back after each guess, such as whether the guess was too high, too low, or correct.

Example

Think of a number guessing game where a friend picks a number from 1 to 100 and says higher or lower after each guess. If you guess 50 and hear higher, you know the answer is between 51 and 100, so you ignore everything from 1 to 50. You keep guessing the middle of what is left, and the range shrinks fast.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part shows how bisection search finds a square root by cutting the search range in half on every guess, and why that is far faster than trying numbers one at a time.

Key ideas

After each guess, you update one boundary. If the guess is too high, the high end becomes the guess. If it is too low, the low end becomes the guess. 30:00
Each time through the loop, the new guess is the midpoint of the current low and high ends. You check it, then move one end to it. 30:45
To find the square root of 36, the guesses go 18, then 9, then 4.5, then 6.75, and so on. Each guess gets closer, until the guess squared is within epsilon of 36. 32:33
Bisection search needed about 30 guesses and under a second for the square root of 54,321. The slower approximation method needed about 23 million guesses and about 20 seconds. 35:53
Because the search space is cut in half each time, the number of guesses grows as log of n. Doubling the size of the problem adds only one more guess. 39:05

Words to know

bisection search: A way of finding an answer by guessing the middle of a range, then keeping only the half that still holds the answer.
epsilon: The small amount of error you accept. If your answer is within epsilon, you call it close enough.
logarithmic growth: When the work needed grows very slowly compared with the size of the problem. Each extra step covers twice as much ground.
while loop: A block of code that keeps repeating as long as a condition is still true, and stops when it becomes false.

Example

Imagine finding one page in a 400-page book by opening to the middle and then always going to the half that still has the page. After one check you have 200 pages left, then 100, then 50. Bisection search works the same way with numbers.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–50:00

This part explains why a bisection search program got stuck in an endless loop, how to fix its starting range, and why bisection search is so fast.

Key ideas

The program ran forever, which is called an infinite loop. The fix was to add print statements inside the loop so the values could be seen while it ran. 40:00
When x is between 0 and 1, the square root of x is bigger than x. Starting with low at 0 and high at x does not bracket the answer, so the guesses get stuck. 41:42
Computers store decimals with small rounding mistakes, called floating point errors. Because of these, the low and high values eventually both land on exactly 0.5, and the guess never changes. 43:37
The fix is to choose better starting endpoints. If x is less than 1, set low to x and high to 1, since the square root must lie between those two numbers. Adding an if and else lets the code handle any input. 46:20
Bisection search solves the problem much faster than the approximation method and gives an answer that is just as good. Each guess cuts the remaining range in half, so the steps get smaller over time. 48:47

Words to know

infinite loop: A loop that never stops because its stopping condition is never reached, so the program keeps repeating the same steps.
floating point error: A tiny rounding mistake that happens because computers cannot store every decimal number exactly.
bisection search: A way of finding an answer by repeatedly guessing the middle of a range and throwing away the half that cannot hold the answer.
logarithmic growth: A pattern where each step makes a smaller and smaller improvement, so the results level off over time.

Example

Imagine finding a page in a 1,000-page book by opening it to the middle. If the page is too far ahead, you throw away the back half and repeat with the front half. The lesson's book example works this way: the first guess removed 200 pages, the next removed 100, then 50, and so on, so the search gets very close to the answer quickly.

3 checked practice questions for this part are in the app.

Part 6 · 50:00–1:00:00

This part shows how to write a bisection search that finds a cube root, and introduces Newton-Raphson, another way to get closer to a root.

Key ideas

Bisection search only works when the search space has endpoints, is in order, and you can get feedback on whether a guess is too low or too high. Without those, you cannot use it. 50:18
To find the cube root of 27, start with a low of 0 and a high of 27, then guess the middle value. Keep looping while the guess cubed is still farther than epsilon (0.01) from 27. 51:03
Use a 'keep going while still too far away' test instead of checking for exact equality, because comparing decimal numbers exactly is unreliable. If the guess is too high, move the high end down to the guess. If it is too low, move the low end up to the guess. 53:00
The program stops as soon as the guess is within epsilon, so the printed answer may be close to 3 but not exactly 3. That is the result the code was asked to produce. 56:16
Newton-Raphson improves a guess using a formula that involves a polynomial and its derivative. To find the square root of 24, you treat x squared minus 24 as the polynomial to solve. 59:14

Words to know

bisection search: A way of finding an answer by repeatedly guessing the middle of a range and cutting the range in half, based on whether the guess is too high or too low.
epsilon: A small margin of error. The answer counts as good enough when it is within this distance of the target.
polynomial: A math expression made of powers of x added together, such as x squared minus 24.
derivative: A formula that shows how fast a polynomial is changing at a given point. Newton-Raphson needs it to pick a better guess.

Example

Imagine guessing a secret number between 1 and 100, and a friend tells you 'higher' or 'lower' after each guess. If you always guess the middle of the range that is still possible, you find the number quickly. This matches bisection search: pick the middle, use the feedback, and cut the range in half.

3 checked practice questions for this part are in the app.

Part 7 · 1:00:00–1:10:00

This part shows how a faster guessing method, Newton-Raphson, finds square roots, and previews the big ideas of decomposition and abstraction.

Key ideas

Newton-Raphson improves a guess by taking the current guess and subtracting the polynomial's value at that guess, divided by its derivative (how steeply it is changing) at that guess. Each new guess comes from following a tangent line down to the x-axis. 1:00:00
The loop keeps making new guesses while the guess is still farther than epsilon (a small allowed margin of error) from the true answer. This is the same stopping rule used in the earlier methods. 1:00:00
On the example of finding the square root of 24 within 0.01, Newton-Raphson needed only four guesses. The lesson says that is far fewer than the earlier methods needed. 1:00:00
The method only works for finding square roots, so it is not a general tool for other problems. 1:00:00
Decomposition means splitting a large program into smaller, self-contained parts that can pass values to each other. Abstraction means hiding the details of how a part works, so others only need to know what inputs to give it. 1:00:00

Words to know

derivative: A number that tells you how steeply a line or curve is going up or down at one specific point.
epsilon: A small margin of error. You accept an answer if it is within this distance of the right answer.
decomposition: Breaking one big job into smaller separate pieces that each handle one part of the job.
abstraction: Hiding the messy details of how something works, so you only need to know what goes in and what comes out.

Example

Imagine you are trying to reach the bottom of a valley while blindfolded. At each step you check how steep the ground is where you stand, then aim for the spot where a straight line along that slope would hit the ground, and step there. Each step gets you closer, just as each Newton-Raphson guess gets closer to the square root.

3 checked practice questions for this part are in the app.

Part 8 · 1:10:00–1:14:20

This part explains how breaking code into small reusable pieces and hiding unneeded details makes code easier to fix, maintain, and understand.

Key ideas

Decomposition means splitting code into smaller pieces that each do one job on their own. Like a group project, each piece can be built separately and then put together. 1:10:43
Saving a repeated value, such as 2.2, in a named variable means you type it once. If you need to change it later, you change it in one place instead of many. 1:11:30
Abstraction means hiding details you do not need right now. You only need to know what a piece of code does, not every step it takes to do it. 1:12:16
Comments are a simple way to use abstraction. A short note at the top of your code lets you remember what it does weeks later without reading every line. 1:12:38
Functions are small reusable modules. You write one once, debug it once, and then use it many times with different inputs, instead of copying and pasting the same code. 1:13:40

Words to know

decomposition: Breaking a big job into smaller pieces of code that each do one part of the job.
abstraction: Hiding the details you do not need to see, so you can focus on what a piece of code does.
module: A separate, self-contained piece of code that you can use together with other pieces to reach a shared goal.
function: A small reusable piece of code that you write once and can call again and again with different inputs.

Example

Think of a group project where each person solves one part and then brings their result to the group. You do not need to know how your teammate solved their part, only that they solved it correctly. Abstraction works the same way: you care about what the code gives back, not every detail of how it got there.

3 checked practice questions for this part are in the app.

← Lecture 4: Loops over Strings, Guess-and-Check, and Binary · Lecture 7: Decomposition, Abstraction, and Functions →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York