A searching algorithm is designed to find a specific item or location within a data structure. It involves systematically examining elements in a dataset to determine whether a particular element matches the search criteria.
Based on the type of search operation, these algorithms are generally classified into two categories:
Linear Search is defined as a sequential search algorithm that starts at one end and goes through each element of a list until the desired element is found, otherwise the search continues till the end of the data set.
In Linear Search Algorithm,
O(1), If the recursive call stack is considered then the auxiliary space will be O(logN).
These algorithms are specifically designed for searching in sorted data-structures. These type of searching algorithms are much more efficient than Linear Search as they repeatedly target the center of the search structure and divide the search space in half.
Conditions for when to apply Binary Search in a Data Structure:
O(1), If the recursive call stack is considered then the auxiliary space will be O(logN).
Binary search can be used as a building block for more complex algorithms used in machine learning, such as algorithms for training neural networks or finding the optimal hyperparameters for a model. It can also be used for searching in computer graphics, such as algorithms for ray tracing or texture mapping, and for searching a database.
Comparison | Linear Search | Binary Search |
---|---|---|
Search Algorithm | Sequential search algorithm. | Algorithm used in a sorted array by repeatedly dividing the search interval in half. |
Time Complexity (Average Case) | O(N) | O(log N) |
Efficiency | Slower, especially for large arrays. | Faster, especially for large arrays. |
Data Structure | Can be used on arrays of any data type, whether sorted or not. | Requires the data structure to be sorted for efficient searching. |
Memory Usage | Does not require additional memory. | Requires O(1) auxiliary space. |