Past exam question: 2075 Baisakh (Back), Q8
Open in the Padhaiko appQuestion
Compare sequential search with binary search. Discuss about linear probing and quadratic probing.
Solution
Sequential Search vs. Binary Search:
| Aspect | Sequential (Linear) Search | Binary Search |
|---|---|---|
| Precondition | Works on sorted or unsorted data | Requires sorted random-access array |
| Method | Checks elements one by one from index 0 | Halves search space at middle element each step |
| Best / Worst Time | / | / |
| Data Structure | Arrays and linked lists | Contiguous sorted arrays (not standard linked lists) |
Linear Probing vs. Quadratic Probing (Open Addressing):
- Linear Probing: On collision at , probes ().
- Pros: Simple, good CPU cache locality, always finds an empty slot if load factor .
- Cons: Suffers primary clustering—contiguous occupied blocks merge and grow, slowing searches toward .
- Quadratic Probing: On collision at , probes (commonly ).
- Pros: Eliminates primary clustering by jumping across the table with quadratic strides.
- Cons: Suffers mild secondary clustering (keys sharing the same home hash follow identical probe paths) and may fail to probe all slots unless is prime and load factor .
Answer:
- Sequential vs. Binary Search: Sequential search takes on any list; binary search takes on sorted arrays.
- Linear vs. Quadratic Probing: Linear probing steps sequentially () causing primary clustering; quadratic probing steps quadratically (), avoiding primary clustering at the cost of secondary clustering and stricter table-size rules.