Searching is a technique that is used to check whether the given element is present or not in the given list of elements.
If the search element is present in the given list of elements then it is called a successful search otherwise it is an unsuccessful search.
- Searching is a fundamental operation in DSA.
- Different algorithms are suited for different data structures and scenarios.
- Choosing the right algorithm can significantly impact search efficiency.
- Understanding searching techniques is essential for software developers and computer scientists.
Searching Algorithms Types
Table of Contents
Searching Terminologies for Linear, Binary, and Fibonacci Algorithms
Linear Search Terminology
- Sequential Search: Synonymous with linear search, highlighting the step-by-step nature of the algorithm.
- Iteration: A single step in the linear search process, where one element is compared to the target.
- Traversal: The complete process of iterating through the data structure.
- Unsuccessful Comparison: This occurs when the current element being examined doesn’t match the target.
Binary Search Terminology
- Sorted Data: A prerequisite for binary search, ensuring elements are in ascending or descending order.
- Midpoint: The middle element of the current search interval, calculated as (low + high) / 2.
- Left Subarray (Lower Half): The portion of the array to the left of the midpoint, where the search continues if the target is smaller than the midpoint.
- Right Subarray (Upper Half): The portion of the array to the right of the midpoint, where the search continues if the target is larger than the midpoint.
- Recursive Call: Binary search often uses recursion to repeatedly divide the search interval.
Fibonacci Search Terminology
- Fibonacci Numbers: The sequence 0, 1, 1, 2, 3, 5, 8… where each number is the sum of the two preceding ones.
- Elimination Ratio: Approximately 1.618 (the Golden Ratio), representing the portion of the array eliminated in each step.
- Two Fibonacci Numbers: Used to define the initial search range, typically the two largest Fibonacci numbers smaller than or equal to the array size.
Note
- Linear Search: Simple, sequential search suitable for unsorted data.
- Binary Search: Highly efficient for sorted data, logarithmic time complexity.
- Fibonacci Search: Similar to binary search but with a unique elimination pattern based on Fibonacci numbers.