Searching

[peppapig450]

The next optimizing/benchmarking shall be searching.

We shall test the following

1.  Binary Search:
•   Best for: Sorted arrays or lists.
•   Time complexity: O(\log n)
•   Description: Divides the search interval in half repeatedly to quickly locate the target value.
2.  Hash Table Lookups:
•   Best for: Unsorted data with key-value pairs.
•   Average time complexity: O(1)
•   Description: Uses a hash function to map keys to indices in an array, allowing for constant-time average lookups.
3.  Binary Search Trees (BST):
•   Best for: Data that can be dynamically updated with insertions and deletions.
•   Average time complexity: O(\log n) for balanced trees (e.g., AVL trees, Red-Black trees)
•   Description: Maintains a sorted structure where each node has two children, allowing for efficient searching, insertion, and deletion.
4.  Balanced Search Trees (e.g., AVL Trees, Red-Black Trees):
•   Best for: Dynamic datasets where maintaining sorted order is crucial.
•   Time complexity: O(\log n) for search, insertion, and deletion.
•   Description: Self-balancing binary search trees that ensure the tree remains balanced after operations, keeping search times efficient.
5.  Trie (Prefix Tree):
•   Best for: Searching strings or sequences, especially for prefix-based searches.
•   Time complexity: O(m), where m is the length of the key.
•   Description: A tree-like data structure where each node represents a character of the key, allowing efficient retrieval of keys.
6.  Bloom Filter:
•   Best for: Fast membership testing with a small probability of false positives.
•   Average time complexity: O(k), where k is the number of hash functions.
•   Description: A space-efficient probabilistic data structure that uses multiple hash functions to test whether an element is a member of a set.

Summary

•   For sorted arrays/lists: Binary Search.
•   For key-value pairs: Hash Table.
•   For dynamic data with sorted order: Balanced Search Trees (e.g., AVL Trees, Red-Black Trees).
•   For prefix-based string searches: Trie.
•   For probabilistic membership testing: Bloom Filter.

[peppapig450]

the formatting got messed up from mobile