Searching: binary search, interpolation search

Here we present some approaches for searching certain linear structures.

Readings: Textbook, chapter 7 (searching)

Supplemental materials:

Comprehension check:

1. Given an unsorted vector or linked list, linear search has a complexity of __________.
2. If we have a sorted vector, we can achieve O(log n) search complexity using ________________.
3. If a structure has random access it means that we can access any element in that structure via some index. Which of the following sorting methods requires random access: linear search, binary search, interpolation search.
4. If data are more-or-less uniformly distributed, then we can make very good guesses about where to find data within a linear structure. One method that takes advantage of this is ________________.
5. Under the right conditions, interpolation search can achieve performance of O(____________).

Answers: u 苾ol 苾ol / 丧蓴晒蓯菨s uo岽壥嚿恖od晒菨蕠u岽� / 丧蓴晒蓯菨s uo岽壥嚿恖od晒菨蕠u岽� pu蓯 丧蓴晒蓯菨s 蕩晒蓯u岽塹 / 丧蓴晒蓯菨s 蕩晒蓯u岽塹 / (u)O

Copyright 漏 2023鈥�2025 Clayton Cafiero

No generative AI was used in producing this material. This was written the old-fashioned way.