Imagine looking for a particular baseball card in a binder. Search asks whether the target is there and, if it is, where to find it. Sorting the cards first takes work, but can make repeated searches easier. Here, a match means the requested value or key—not a merely similar one. section 3.2 section 2.13 section 12.3
How you search depends on how the collection stores its data:
- In an unsorted array, check entries one by one. Return the first matching index, or None if none matches. section 2.13
- In a sorted array, stop scanning when an entry exceeds the target: everything after it is larger too. A target near the end can still require a long scan. section 3.6
- In a linked list, follow nodes until a match or the end. An internal search can return a node, but clients should not need access to nodes. section 6.8
- In a binary search tree, compare at each node and follow only the possible branch. Search takes at most one root-to-leaf path, so its cost depends on tree height. section 11.8
Stopping an unsuccessful search
Suppose a sorted array is being searched for 8. Once the scan reaches 9, it can return None without checking later entries. By contrast, an unsorted array offers no such stopping rule. section 3.6 section 2.13
def find(self, target):
for index in range(0, self._size):
if self._array[index] == target:
return index
return None #1
#1 If it got to this point, it couldn’t find the target.
The Python loop checks each occupied array entry, returns the first matching index, and returns None only after the scan ends. section 2.13
Search also supports other operations: finding an array value gives its index for deletion, while a dictionary retrieves a value by key. Hash-table chaining still searches within a bucket; if many keys land there, that scan can be long. These are exact-match searches, not methods for ranking results by similarity. section 2.13 section 12.3 section 12.18
