Searching Algorithms

Searching Algorithms Overview

• Searching is the process of finding an item with specific properties within a collection of items
• Items can be stored in databases, arrays, files, trees, graphs, or other search spaces

Why Searching Algorithms are Essential

• Searching is a core computer science algorithm
• Efficient searching algorithms are needed to proficiently retrieve information
• Organizing data in certain ways improves the efficiency of the searching process
• Keeping data in proper order makes it easier to search for a required element

Types of Searching Algorithms

• Unordered Linear Search
• Sorted/Ordered Linear Search
• Binary Search
• Binary Search Trees

Unordered Linear Search

• Assumes the array's elements are not sorted
• Requires scanning the entire array to find an element
• O(n) time complexity occurs in the worst-case scenario, requiring a full array scan

Sorted/Ordered Linear Search

• Elements in the array are already sorted
• Scanning the entire array is not required in many cases
• If a value exceeds the search data, return -1 without searching the remaining array

Ordered Linear Search

• O(n) time complexity in the worst case
• Reduces complexity in the average case

Binary Search

• Mimics searching for a word in a dictionary by going to an approximate page
• If the word is on the page, the search is complete
• Apply the same process to the first half if the page is before, or the second half if after
• Uses an iterative or recursive method
• O(log n) time complexity

Comparing Basic Searching Methods

• Unordered Array: n worst-case, n/2 average-case
• Ordered Array (Binary Search): log n worst-case, log n average-case
• Unordered List: n worst-case, n/2 average-case
• Ordered List: n worst-case, n/2 average-case
• Binary Search Trees (for skew trees): n worst-case, log n average-case

String Algorithms

• Browsers display a list of possible URLs upon typing a prefix by using auto-completion
• Data structures are needed to store the string data efficiently

String Matching Algorithms

• Focus on checking if a pattern P is a substring of another string T
• These algorithms are called exact string matching algorithms
• Assumes the length of T is n, and the length of P is m
• T has characters from 0 to n – 1 (T[0... n – 1]) and P has characters from 0 to m – 1 (T[0... m – 1])
• Implemented in C++ as strstr() and in Python as find()
• Includes the Brute Force Method, Rabin-Karp String Matching Algorithm, and Boyer-Moore Algorithm

Brute Force Method

• Checks each position in text T for a match with pattern P
• If the length of T is n, there are n – m + 1 possible choices for comparisons
• There is no need to check the last m – 1 locations since the pattern length is m

Rabin-Karp String Matching Algorithm

• Hashing is used to check if the hashing of P and m characters of T give the same result
• Use a hash function to the first m characters of T
• If the results are not the same, apply the hash function to the next character of T
• If the results are the same, compare those m characters of T with P

Data Structures for Storing Strings

• Efficient storing of strings are needed for faster search operations
• String sets can be stored using Hashing Tables, Binary Search Trees, Tries, or Ternary Search Trees

Hash Tables for Strings

• Keys are the strings
• Loss of ordering information occurs which results in greater search times
• The hash function takes the complete key and performs a hash on it
• The location of each word is not known

BST (Binary Search Tree) for Strings

• Sorts strings alphabetically
• A is set before B, and B before C, and so on
• Has a natural ordering
• Use a BST to store and retrieve strings

Issues with BST Representation

• Good storage efficiency
• The search operation at every node increases the time complexity
• BST representation of strings is good in terms of storage but not in terms of time

Tries

• A tree that contains a number of pointers equal to the number of characters of the alphabet in each node
• Each node of the tries contains 26 pointers with English alphabet characters "a" to "z" if all the strings are formed with those characters

Why Tries are useful

• Can insert and find strings in O(L) time, where L is the length of a single word
• Faster than hash table and binary search tree representations

Issues with Tries Representation

• High memory usage because there are too many node pointers for each node
• Occupancy of each node is less
• Tries are faster but require a lot of memory for storing strings

Ternary Search Trees

• Takes the advantages of binary search trees and tries
• Combines the memory efficiency of BSTs and the time efficiency of tries

Ternary Search Tree characteristics

• The left pointer points to the TST containing strings that are alphabetically less than the data
• The right pointer points to the TST containing strings that are alphabetically greater than the data
• The eq pointer points to the TST containing strings that are alphabetically equal to the data

Recursive Version Search in TST

• Search follows the same rules of a binary search
• The only difference is in the case of match, check for the remaining characters (in eq subtree)
• The time complexity is O(L), where L is the length of the string to be searched

Non-Recursive Version Search in TST

• Works in the same was as recursive version
• Returns whether search has been successful

Comparing BSTs, Tries, and TSTs

• Hash tables and BSTs store the complete string at each node which takes more time for searching, but they are memory efficient
• TSTs can grow and shrink dynamically, whereas hash tables resize only based on load factor
• TSTs allow partial search, whereas BSTs and hash tables do not support it
• TSTs can display words in a sorted order, whereas hash tables cannot do this
• Tries perform search operations very fast but take a lot of memory for storing strings
• TSTs combine the advantages of BSTs and Tries, and the memory efficiency of BSTs and the time efficiency of Tries