Searching Algorithms
Introduction
Searching is the process of finding a desired element from a collection of available elements. For example, searching for a particular contact number in a phone directory. Desired phone number is called target and the phone directory is called search space. Search algorithms designed to find whether the target exists in the search space or anything. The search space can be an array or a list or it can be a database.
Searching algorithms are mainly classified into two types :
Linear Search
In Linear Search, we sequentially traverse the array to check whether the element is matching with the given target element or not.
Binary Search
Binary Search algorithm works only if the elements of the array has some inherit ordering like elements of the array in ascending order by their values. In Binary Search we compare the middle element of the array with the target element and at each iteration we should be able to reduce the search space into half by using the sorting feature of the array.
Video Explanation
Linear Search Vs Binary Search
| Linear Search | Binary Search |
|---|---|
| Linear Search works even if elements are in random order | Binary Search works only if the elements are in sorted array |
| In Linear Search, elements in the array will be checked one by one until we find the desired element | In Binary Search random element will be checked and based on the values of random element further search process gets executed |
| As elements checked sequentially, it is known as sequential search | every iteration the array size gets reduced to half of its size, so it is known as interval search or logarithmic search |
| Worst case time complexity is O(n) | Worst case time complexity is O(log n) |
| Linear search is efficient if array is smaller in size | Binary search works efficient irrespective of the size of the array |