🔁Data Structures Unit 14 – Searching Algorithms and their Analysis

Key Concepts and Terminology

• Searching algorithms enable efficient retrieval of data from a collection based on specific criteria
• Search key represents the value or property used to identify and locate the desired data element
• Search space refers to the collection of elements being searched, which can be an array, list, or other data structure
• Successful search occurs when the search key is found within the search space and its location or index is returned
• Unsuccessful search happens when the search key is not present in the search space, often indicated by returning a special value (e.g., -1)
• Comparison-based searching algorithms rely on comparing the search key with elements in the search space to determine a match
• Non-comparison-based searching algorithms use alternative techniques (hashing) to locate elements without direct comparisons
• Time complexity measures the number of operations or comparisons performed by a searching algorithm relative to the input size

Types of Searching Algorithms

• Linear search sequentially examines each element in the search space until a match is found or the end is reached
• Binary search efficiently searches sorted arrays by repeatedly dividing the search space in half
• Hash-based searching utilizes hash functions to compute indices and store elements in a hash table for quick retrieval
• Interpolation search improves upon binary search by estimating the position of the search key based on its value
• Exponential search combines binary search with an exponentially increasing search range to handle unbounded search spaces
• Fibonacci search uses Fibonacci numbers to determine the splitting points in the search space, similar to binary search
• Ternary search divides the search space into three parts and recursively searches the appropriate partition
• Sublist search algorithms (Knuth-Morris-Pratt, Rabin-Karp) efficiently search for occurrences of a pattern within a larger text

Linear Search: Implementation and Analysis

• Linear search starts at the beginning of the search space and compares each element with the search key until a match is found or the end is reached
• Implementation involves iterating through the elements using a loop and comparing each element with the search key
• Best-case time complexity is O(1) when the search key is found at the first position
  • Occurs when the desired element is located at the beginning of the search space
• Worst-case time complexity is O(n) when the search key is found at the last position or not present in the search space
  • Requires examining all elements in the worst-case scenario
• Average-case time complexity is O(n) as the search key can be located at any position with equal probability
• Linear search does not require the search space to be sorted, making it versatile for unsorted collections
• Efficiency of linear search deteriorates as the size of the search space increases, making it unsuitable for large datasets

Binary Search: Implementation and Analysis

• Binary search efficiently searches sorted arrays by repeatedly dividing the search space in half
• Requires the search space to be sorted in ascending or descending order
• Starts by comparing the search key with the middle element of the search space
  • If the search key matches the middle element, the search is successful
  • If the search key is less than the middle element, the search continues in the lower half of the search space
  • If the search key is greater than the middle element, the search continues in the upper half of the search space
• The process is repeated recursively or iteratively until the search key is found or the search space is exhausted
• Best-case time complexity is O(1) when the search key is found at the middle position of the search space
• Worst-case and average-case time complexity is O(log n) as the search space is halved in each iteration
• Binary search significantly reduces the number of comparisons compared to linear search, especially for large sorted arrays
• Efficient for searching large datasets that can be sorted and remain static

Hash-based Searching: Concepts and Techniques

• Hash-based searching utilizes hash functions to compute indices and store elements in a hash table for quick retrieval
• Hash function maps the search key to an index in the hash table, aiming to distribute elements uniformly
• Collisions occur when multiple elements hash to the same index, requiring collision resolution techniques
  • Separate chaining handles collisions by storing elements with the same hash value in a linked list or array at the corresponding index
  • Open addressing resolves collisions by probing alternative indices in the hash table until an empty slot is found (linear probing, quadratic probing, double hashing)
• Hash tables provide constant-time average-case complexity for insertion, deletion, and searching operations
• Load factor (ratio of number of elements to hash table size) affects the performance and collision probability
• Rehashing is performed when the load factor exceeds a threshold, requiring resizing the hash table and recomputing indices
• Hash-based searching is efficient for large datasets and provides fast average-case retrieval time
• Suitable for applications that prioritize search speed over sorting requirements

Advanced Searching Algorithms

• Interpolation search improves upon binary search by estimating the position of the search key based on its value
  • Assumes elements are uniformly distributed and calculates the probe position using interpolation formula
  • Efficient for sorted arrays with uniformly distributed elements, providing O(log log n) average-case complexity
• Exponential search combines binary search with an exponentially increasing search range to handle unbounded search spaces
  • Starts with a small range and exponentially increases the range until the search key is located or the range exceeds the array size
  • Performs binary search within the determined range, resulting in O(log n) worst-case complexity
• Fibonacci search uses Fibonacci numbers to determine the splitting points in the search space, similar to binary search
  • Divides the search space into Fibonacci-sized partitions and eliminates the appropriate partition based on comparisons
  • Provides similar performance to binary search with slightly fewer comparisons on average
• Ternary search divides the search space into three parts and recursively searches the appropriate partition
  • Compares the search key with two pivots (one-third and two-thirds) and eliminates one partition based on the comparisons
  • Offers better performance than binary search for certain distributions of elements
• Sublist search algorithms efficiently search for occurrences of a pattern within a larger text
  • Knuth-Morris-Pratt (KMP) algorithm uses a failure function to skip comparisons and achieve O(n) time complexity
  • Rabin-Karp algorithm uses rolling hash functions to efficiently compare patterns and text substrings

Time and Space Complexity Analysis

• Time complexity measures the number of operations or comparisons performed by a searching algorithm relative to the input size
• Space complexity refers to the amount of additional memory required by the algorithm beyond the input data
• Big O notation is used to express the upper bound of time and space complexity, indicating the worst-case scenario
• Linear search has a time complexity of O(n) in the worst and average cases, as it may need to examine all elements
• Binary search has a time complexity of O(log n) in the worst and average cases, as it eliminates half of the search space in each iteration
• Hash-based searching provides an average-case time complexity of O(1) for insertion, deletion, and searching operations
  • Worst-case time complexity depends on the collision resolution technique and can be O(n) in case of many collisions
• Space complexity of searching algorithms is typically O(1) as they require only a constant amount of additional memory
• Advanced searching algorithms (interpolation, exponential, Fibonacci, ternary) have time complexities ranging from O(log log n) to O(log n) in the average and worst cases
• Sublist search algorithms (KMP, Rabin-Karp) have a time complexity of O(n) for searching patterns within a text of length n

Practical Applications and Use Cases

• Database systems employ searching algorithms to efficiently retrieve records based on specified criteria
• Search engines use searching algorithms to quickly find relevant web pages based on user queries
• Dictionaries and phone books implement searching techniques to locate entries based on keywords or names
• Compiler symbol tables utilize hash-based searching to quickly look up identifiers and their associated information
• Plagiarism detection software applies sublist search algorithms to find occurrences of copied content
• Bioinformatics uses searching algorithms to match and align DNA sequences and identify patterns
• Spell checkers employ searching techniques to suggest corrections for misspelled words
• Network routers use searching algorithms to efficiently forward packets based on destination addresses
• Recommendation systems utilize searching algorithms to find similar items or users based on preferences
• File systems implement searching algorithms to locate files and directories based on names or attributes