Search Algorithms: Linear, Binary and Hash

• Covers search algorithms, including linear search, binary search, and hash tables
• Touches on 2-3 trees and Left-Leaning Red-Black Trees (LLRBT) as balanced search tree options

Search Applications

• Various applications use specific search types
• Dictionaries use search to find definitions by word
• Book indexes use search to identify relevant pages by term
• File sharing uses search to locate songs by name
• Financial accounts systems use search to process transactions by account number
• Web search engines use search to find web pages by keywords

Linear/Sequential Search

• Involves maintaining an unordered linked list of key-value pairs
• Requires scanning through all keys until a match is located
• For insertion, if a match is found keys will be scanned, otherwise the new node is added to the front
• The complexity of sequential search in an unordered array is O(N)
• The complexity of inserting into an unordered array is O(N)

Binary Search

• This search algorithm maintains an ordered array of key-value pairs
• Utilizes a 'rank' helper function to determine the number of keys less than k
• Determines the index position of a key if it exists in the array, and if the key is present in the array or the appropriate insertion point if it doesn't
• Binary search has a search complexity of O(log N) in an ordered array
• Insertion complexity in an ordered array is O(N), considering the need to shift elements
• Inserting a key requires shifting all greater keys over

Hash Tables

• An efficient data structure for dynamic sets, supporting simple operations like insert/put, search/get, and delete
• Generalized field structure suitable for applications like Google search and caching
• In the worst-case scenario with linked lists, searching can be O(n)

Direct Addressing Hash Table

• Best used with a relatively small set of keys
• Given a hash table H[0,..., m-1] with m places, m >= k
• Hash Function: h(k) → k maps key k to index k
• Advantage: offers simple implementation of insert, search, and delete
• Disadvantage: impractical for a large number of keys, as the actual number of keys observed k, may be very small compared to the table size m, wasting space
• Solutions of this include using a hash function with collision resolution, separate chaining, and probing

Hash Function with Collision

• Restricts the size of the hash table by mapping a set of possible keys to a smaller set m
• Problem with Collisions: Two distinct keys being hashed onto the same hash code
• E.g., the Mod7 function makes any integer key to the range [0 … 6], Mod7(15)=1, Mod7(22)=1

Design of Good Hash Functions

• Objective is to achieve a good distribution of the search key k to the index range of the hash table H, without underlying assumptions about a probability distribution

Division Method / Modular Hashing

• The hash function h is defined as h(k) = k mod m, where m is the size of the hash table H
• For instance, if m = 12 and k = 100, then h(100) = 4
• Good candidates for m are prime numbers

Separate Chaining

• Also known as open hashing or closed addressing
• Uses an array of size m < k linked lists
• Hash: Maps a key to an integer i between 0 to m-1
• Insert: Puts the new node at the front of the ith chain if it's not already there
• Search: Needs to search only the ith chain

Separate Chaining - Resizing

• The goal is to keep the average length of the list k/m constant
• Double the size of array M when k/m >= 8
• Halve the size of array M when k/m <= 2
• Need to rehash all keys when resizing

Further Topics in Search Algorithm

• Terminologies of tree structures such as 'forests', 'degree of node', 'leaf node', 'depth of node', 'height of node'
• BST
• Balanced search tree
• 2-3 tree and related transformations and properties
• Red-black trees and "glue" nodes

Note that there is no material related to deletion of hash table entries or separate chaining entries in this study guide. Probing, quadratic and double hashing, and complexity analysis are also missing.