Searching algorithms are used to find the presence or location of a specific element within a collection of data.
They play a crucial role in various applications, such as databases, information retrieval systems, and problem-solving tasks.
Here are some commonly used searching algorithms:
1. Linear Search:
- Description: Linear search sequentially checks each element in the data collection until the target element is found or the entire collection has been traversed.
- Time Complexity: O(n) in the worst case, where n is the size of the collection.
2. Binary Search:
- Description: Binary search is a divide-and-conquer algorithm that works on a sorted collection. It repeatedly divides the search space in half and compares the target element with the middle element to determine which half to focus on.
- Time Complexity: O(log n) in the worst case, where n is the size of the sorted collection. Note that the collection must be sorted for binary search to work.
3. Interpolation Search:
- Description: Interpolation search is an improvement over binary search for uniformly distributed data. It uses interpolation to estimate the position of the target element by considering the values of the endpoints.
- Time Complexity: O(log log n) on average for uniformly distributed data, but it can degrade to O(n) in the worst case.
4. Hashing:
- Description: Hashing is a technique that uses a hash function to map keys to array indices. By hashing the key, direct access to the value associated with the key can be achieved in constant time.
- Time Complexity: O(1) on average for a well-designed hash function, but it can be O(n) in the worst case if there are many collisions.
5. Ternary Search:
- Description: Ternary search is a divide-and-conquer algorithm similar to binary search but divides the search space into three parts instead of two. It is useful when the collection is sorted and the target element may appear in any of the three segments.
- Time Complexity: O(log₃ n) in the worst case, where n is the size of the collection.