Revision Guide: Searching

Searching locates a specific element in a collection to check its presence and position.

Compares each element sequentially with the key. Useful for small, unordered lists.

Worst-case time complexity is O(n). Every element is checked until the key is found or the list ends.

1. Start at index 0. 2. Check each element. 3. Stop if found; report 'not found' otherwise.

Efficiently finds a key in a sorted list by repeatedly dividing the search interval in half.

List must be sorted. It compares the target with the middle element to narrow down the search.

1. Set first and last. 2. Calculate mid index. 3. Compare mid element with the key.

Time complexity is O(log n). Each comparison discards half the remaining elements.

A technique that uses a hash function to map keys to specific positions in a hash table.

Commonly, h(element) = element % size(hash table). Maps element to an index for quick access.

Occurs when two elements hash to the same index. Requires collision resolution strategies.

Maps unique keys to unique indices. No collisions occur, ensuring efficient searching.

Used in searching dictionaries, databases, and indexing to quickly locate items.

Linear search is simple for small datasets; binary search is efficient for larger sorted datasets.

The key is the element being searched. The search stops when the key is found or not present.

Binary search can be implemented both iteratively (using loops) and recursively (function calls).

Used in database indexing, password storage, and data retrieval where speed is crucial.

Linear search is less efficient than binary search, especially as the dataset size increases.

Be able to evaluate your search implementation through testing with varied datasets for accuracy.

The dataset must be sorted before applying binary search. Use sorting algorithms first.

Each comparison during the search refines the potential location of the key significantly.