Many times we come across questions that require us to check for an element or retrieve its position in the array.
In such questions, using an effective Search Algorithm helps us in reducing the time complexity of our code.
There are two types of Search Algorithms:
- Sequential Search
- Interval Search
Sequential Search:
Here, we traverse through all the elements sequentially and check all the elements.
Eg- Linear Search.
Interval Search:
Here, the array is divided into 2 or 3 intervals at every stage. After dividing the array into intervals, we determine the interval at which the element to be found is expected and further divide that interval into 2 or 3 sub-intervals and follow the same process until the length of the sub-interval becomes 0.
Eg- Binary Search, Ternary Search.
SEQUENTIAL SEARCH vs INTERVAL SEARCH
|
SEQUENTIAL SEARCH |
INTERVAL SEARCH |
| The array is traversed sequentially. | The array is divided into sub-intervals and traversed as per the sub-intervals. |
| This works for both sorted as well as unsorted arrays. | This works only for sorted arrays. |
|
As we traverse through all the array elements, the time complexity is more. Time Complexity is O(n) |
As we traverse only through the expected interval at every stage, there is no need to check the remaining intervals. This reduces the time complexity. Binary Search : O(log2n) Ternary Search : O(log3n) |
| Eg : Linear Search |
Eg : Binary Search, Ternary Search |
Which algorithm is the best?
When given a sorted array, using an Interval Search would do the job in less time.
When given an unsorted array, rather than sorting the given array which takes O(nlogn) time complexity and using Interval search, using Sequential Search would do the job in O(n) time complexity.