Compare linear search and binary search on sorted data.
What You Will Learn
Linear search checks elements sequentially and works on unsorted sequences in O(n). Binary search repeatedly halves a sorted search interval for O(log n) comparisons, but requires random access and an ordering consistent with the target.
Sorting data first has its own cost; a one-time search of an unsorted list may favor linear scanning.
Time complexity assumes a specific input structure. Include setup work such as sorting or building a lookup table when comparing complete solutions.
Step-by-Step Example
The example below makes the behavior visible with small input values that you can change safely.
from bisect import bisect_left
numbers = [2, 4, 6, 8, 10]
target = 8
linear_position = next((index for index, value in enumerate(numbers) if value == target), -1)
binary_position = bisect_left(numbers, target)
print(linear_position)
print(binary_position if binary_position < len(numbers) and numbers[binary_position] == target else -1)How the Example Works
- The imports provide the standard-library tools used in the demonstration: bisect.
- The variable numbers holds the result of [2, 4, 6, 8, 10]. Later lines use that value or inspect how it changes.
- The variable target holds the result of 8. Later lines use that value or inspect how it changes.
- The print() calls make the return values or state visible so you can compare them with the explanation and check your prediction.
Expected output from the example:
3
3When You Would Use This
This technique matters when a program handles larger queues, sorted records, or repeated lookups. Choose the data structure based on actual operations and the preconditions the algorithm requires. Verify boundary inputs before optimizing for speed.
Practice: Modify the Code
Find a missing target and compare the two search methods.
Verify the changed output against the behavior described above, including the relevant invalid or boundary case.
For complete parameters and version details, consult the official Python documentation.
Common Beginner Mistakes
- Calling bisect_left() on unsorted data or assuming its insertion index confirms the item exists.
- Overlooking this documented constraint: binary search repeatedly halves a sorted search interval for O(log n) comparisons, but requires random access and an ordering consistent with the target.
Key Takeaways
- Compare linear search and binary search on sorted data.
- Linear search checks elements sequentially and works on unsorted sequences in O(n).
- Sorting data first has its own cost; a one-time search of an unsorted list may favor linear scanning.