Binary search
Halve the problem every step. Find one item in a million in about 20 checks.
Code runs right here in your browser. Nothing to install.
Learn it
Binary search halves a sorted list each step.
If a list is sorted, you can search much faster. Binary search looks at the middle item. If it is the target, done. If the target is smaller, throw away the right half; if bigger, throw away the left half. Repeat on the half that is left.
Each step halves the search area. A list of 1,000,000 items needs at most about 20 steps, because 2 to the power 20 is just over a million. Linear search might need a million.
You track the search area with two positions, low and high, and keep going while low <= high.
def binary_search(items, target): low = 0 high = len(items) - 1 while low <= high: mid = (low + high) // 2 print("checking position", mid) if items[mid] == target: return mid elif items[mid] < target: low = mid + 1 else: high = mid - 1 return -1 nums = [3, 8, 15, 21, 34, 42, 57, 63, 78, 91] print("found at", binary_search(nums, 63))
Try it yourself
+10 XPCount the steps. Change binary_search to return a tuple (position, steps). Search a sorted list of the numbers 0 to 999,999 for 777777 and print the result. It should take 20 steps or fewer.
Create a free account to start this lab
Sign in to write, run and check your code here. Your progress, XP and code are saved to your account. No card needed.
Capture the flag
+10 XPWhat must be true about a list before you can use binary search on it?
Create a free account to start this lab
Sign in to answer the flag question. Your progress, XP and code are saved to your account. No card needed.
Higher or lower bot
+20 XPThe computer must guess a secret number between 1 and 100 using binary search. The test answers each guess with higher, lower or correct. Print each guess like Is it 50?, and finish with Got it in 3 guesses! (with the real count).
Create a free account to start this lab
Sign in to do this homework and have it checked. Your progress, XP and code are saved to your account. No card needed.