BeginnerTopic 17 of 104Software & Computing
Linear and binary search
Binary search halves a sorted list each step for O(log n).
In depth
Linear search checks each item in O(n). Binary search needs sorted data and halves the interval each step in O(log n): 1 million items need about 20 comparisons. Variants find insertion points and boundaries. Hash tables give average O(1) lookup.
Key points
- Midpoint calculation avoids overflow
- Sorted precondition
- Interpolation search
ExampleFinding a name in a sorted phone book of 1M entries needs about 20 look-ups.
What is Linear and binary search?
Binary search halves a sorted list each step for O(log n).
Why is it important to understand linear and binary search?
Searching is one of the most common operations, and the difference between linear and binary search matters greatly for large sorted data.
What is the requirement for binary search?
The data must already be sorted, and each step halves the remaining range, which gives logarithmic time.
When is linear search better?
For small or unsorted data, where sorting first would cost more than scanning, or when items change often.
How is Linear and binary search used in practice?
Typical applications include finding a record in a sorted list of customers, checking whether a value is present in a large table and locating a timestamp in a sorted log file.
What should I learn before Linear and binary search?
Study "Big-O notation" first (topic 16 of 104 in Software & Computing). It covers the groundwork this topic builds on.
What are the key points of Linear and binary search?
Midpoint calculation avoids overflow. Sorted precondition. Interpolation search.
Can you give an example of Linear and binary search?
Finding a name in a sorted phone book of 1M entries needs about 20 look-ups.
What comes after Linear and binary search?
The next topic is "Sorting algorithms", which builds directly on this one.
How difficult is Linear and binary search?
It is classed as Beginner in Software & Computing (topic 17 of 104). It is an entry-level topic. It relies only on basic school mathematics and the ideas introduced earlier in this discipline.