Definition
How do you find a word in a dictionary without reading every page?
Linear search checks items one by one from the start until it finds the target or reaches the end; it works on any list. Binary search works only on a sorted list: it compares the target with the middle item and throws away the half that can't contain it, repeating until it is found or nothing is left.
In simple words
Looking for a friend in a messy crowd, you check face by face: that's linear search. Looking up 'mango' in a dictionary, you open the middle, see 'kite', and know mango is in the second half. Each look halves what's left, so even a 1,000-page dictionary takes about ten looks.
Overview
- Searching means finding whether a value is in a collection and, if so, where.
- Linear search checks items one by one and works on any list, sorted or not.
- Binary search halves a sorted list at each step, so it needs at most about log₂ n checks.
- For 1,000,000 sorted items, linear search may need 1,000,000 checks; binary search needs about 20.
- Python's in, list.index() and the bisect module provide ready-made searches.
- Hash-based lookups in sets and dictionaries take about the same time however large the data.
Why it matters
Searching is everywhere: finding a user, a word, a file. Binary search shows how a smarter method beats a faster computer, an idea that runs through all of algorithm design and AI.
Key terms
- Linear search
- Checking items one by one until the target is found.
- Binary search
- Repeatedly halving a sorted list to find a target.
- Target
- The value being searched for.
- Precondition
- Something that must be true before an algorithm can work, such as a sorted list for binary search.
- Midpoint
- The middle position checked at each step of binary search.
- Logarithmic time
- Work that grows very slowly, adding one step each time the input doubles: O(log n).
Types
There are several searching methods, each suited to a different kind of data. These five are the most important.
1. Linear (sequential) search
Checking each item from the start until the target is found or the list ends.
- How it works: Compare the target with item 0, 1, 2 and so on; return the index when they match, or -1 at the end; time O(n).
- Example: Finding a friend's name in an unsorted attendance list.
- When to use it: Use it for small or unsorted lists, or when you search only once.
2. Binary search
Repeatedly halving a sorted list by comparing the target with the middle item.
- How it works: Keep low and high indexes; check mid = (low + high) // 2; if the target is smaller, search the left half, otherwise the right; time O(log n).
- Example: Finding a word in a dictionary book by opening it in the middle and moving left or right.
- When to use it: Use it on sorted data that you search many times; the bisect module does it for you.
3. Jump search
Jumping ahead in fixed blocks through a sorted list, then searching linearly inside one block.
- How it works: With block size about √n, jump until an item exceeds the target, then step back through that block; time O(√n).
- Example: In 10,000 sorted records, jump 100 at a time, then check at most 100 records.
- When to use it: Use it when jumping forward is cheap but going backwards is costly, as on some storage media.
4. Interpolation search
Guessing where the target probably is from its value, like opening a phone book near "S" for Sharma.
- How it works: It estimates the position as low + (target − a[low]) × (high − low) ÷ (a[high] − a[low]); on evenly spread data it averages O(log log n) checks.
- Example: Looking up roll number 7,500 among roll numbers 1 to 10,000 starts near three-quarters of the way through.
- When to use it: Use it on large, sorted, evenly distributed numeric data; it is slow on skewed data.
5. Hash-based lookup
Finding a value by computing where it is stored from the value itself, as sets and dictionaries do.
- How it works: A hash function turns the key into a bucket number, so a lookup goes almost straight to the right place; average time O(1).
- Example: "Pune" in visited_cities, where visited_cities is a set of 10,000 names.
- When to use it: Use it when you look up items by exact key many times; it cannot find ranges or nearest values.
Explained in detail
Linear search: simple and universal
Linear search starts at the beginning and checks every item until it finds the target or reaches the end. It works on any list, sorted or not, and for short lists it is perfectly good. Its weakness is scale: in the worst case, when the target is last or absent, it checks every item, so a list ten times longer takes ten times longer. Python's in operator and the index() method use linear search on lists.
Binary search: the dictionary method
When you look up a word in a printed dictionary, you do not start at page one. You open near the middle, see whether your word comes before or after, and repeat in the half that remains. Binary search does exactly this. It keeps two markers, low and high, around the part of the list that could still contain the target. It checks the middle item: if it is the target, done; if the target is smaller, move high to just before the middle; if larger, move low to just after it. Each check throws away half of what is left.
How big the difference is
| List size | Linear search, worst case | Binary search, worst case |
|---|---|---|
| 10 | 10 checks | 4 checks |
| 1,000 | 1,000 checks | 10 checks |
| 1,000,000 | 1,000,000 checks | 20 checks |
| 1,000,000,000 | 1,000,000,000 checks | 30 checks |
Doubling the list adds just one step to binary search. That is logarithmic growth, written O(log n), compared with O(n) for linear search. The catch is the precondition: the list must be sorted. Sorting costs time, so binary search pays off when you sort once and search many times, as databases and search indexes do.
Getting binary search right
- Binary search is famous for subtle bugs. The computer scientist Jon Bentley reported in the 1980s that most professional programmers he tested got it wrong on the first try.
- Use while low <= high, not <, or you may miss the last remaining item.
- Always move low to mid + 1 or high to mid - 1; leaving them at mid can loop forever.
- Test with the target at the start, middle, end, and absent, and with lists of length 0, 1 and 2.
- In practice, Python's bisect module provides a tested binary search.
How it works
low ← 0, high ← last index
while low ≤ high:
mid ← (low + high) // 2
if items[mid] = target: found
if items[mid] < target: low ← mid + 1
else: high ← mid − 1
not found| List size | Linear search, worst case | Binary search, worst case |
|---|---|---|
| 10 | 10 checks | 4 checks |
| 1,000 | 1,000 checks | 10 checks |
| 1,000,000 | 1,000,000 checks | 20 checks |
In code
Both searches, each counting how many items it checks.
def linear_search(items, target):
checks = 0
for index, item in enumerate(items):
checks += 1
if item == target:
return index, checks
return -1, checks
def binary_search(items, target):
low, high, checks = 0, len(items) - 1, 0
while low <= high:
mid = (low + high) // 2
checks += 1
if items[mid] == target:
return mid, checks
if items[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1, checks
names = sorted(["Zoya", "Aarav", "Meera", "Kabir", "Sana", "Ishaan", "Diya", "Rohan"])
print(names)
print("Linear search for Sana:", linear_search(names, "Sana"))
print("Binary search for Sana:", binary_search(names, "Sana"))
numbers = list(range(1, 1001))
print("Linear, 1000 items, target 999:", linear_search(numbers, 999)[1], "checks")
print("Binary, 1000 items, target 999:", binary_search(numbers, 999)[1], "checks")Output
['Aarav', 'Diya', 'Ishaan', 'Kabir', 'Meera', 'Rohan', 'Sana', 'Zoya'] Linear search for Sana: (6, 7) Binary search for Sana: (6, 3) Linear, 1000 items, target 999: 999 checks Binary, 1000 items, target 999: 9 checks
Try it yourself
Binary search, step by step
Search for 23 in [3, 8, 12, 17, 23, 31, 40]. Put the steps in order.
- 1Look at 23. It matches, so the search is over after 3 checks.
- 2Look at the middle of what's left, 31. 23 is smaller, so keep the left part: [23].
- 3Look at the middle item, 17. 23 is bigger, so keep the right half: [23, 31, 40].
Common mistakes
- Running binary search on an unsorted list. It gives wrong answers.
- Getting the boundaries wrong and looping forever. Move low to mid + 1 and high to mid − 1.
- Sorting a list just to search it once. Sorting costs more than one linear search.
Check yourself
Summary
- Linear search checks items one by one; it works on any list.
- Binary search halves a sorted list each step.
- For a million items: up to a million checks against about twenty.
Finished reading?
Sources: W3Schools DSA: Binary Search · W3Schools DSA with Python