Searching is a technique used to find the specific element in the given list. It is similar to how we do searching in our daily lives. Searching algorithms are used to find a particular data in the computer.
For example :- Searching is used in Ms-Word for searching a particular element or character in the whole document.
In this technique, the element to be found is searched sequentially in the list from beginning to the end till the location where the element is found. It compares the element to be searched with all the elements present in the array and when the element is matched successfully, it returns the index of the element in the array, else it returns the value of -1.
For example:
In the linear search, if we have to find the element 23, then
- We compare the search element by the first element i.e. 20, element not found
- Now, we compare the search element by the second element i.e. 15, element not found
- Now, we compare the search element by the third element i.e. 23, element found
- As element has been found, now we don’t compare the further elements by search element.
- If the element have not been found while searching the whole array, then it will display the result -1
ALGORITHM OF LINEAR SEARCH
COMPLEXITY OF LINEAR SEARCH
- Best Case Complexity : The best case complexity of linear search will be O(1) as the best case will be the one where the element would be found at first location in array.
- Worst Case Complexity : The worst case complexity of linear search will be O(n) as the worst case will be the one where the element is either found at last location in array or the element is not found in the array.
- Average Case Complexity : The average case complexity of linear search will be O(n) too.
DISADVANTAGES OF LINEAR SEARCH
If the size of the list is very large and element is either not present in the list or it is present at last location, then the complexity of the algorithm will be very high as the search element has to be compared with all the elements in the list.
Binary search is searching any element in a sorted array by repeatedly dividing the search interval into two halves and the item is compared with the middle element of the list. If the match is found then, the location of middle element is returned otherwise, we search into either of the halves depending upon the result produced through the match.
STEPS OF BINARY SEARCH
- Select an element to be searched.
- Find the middle element of the array.
- Compare the search element with the middle element.
For example:
ALGORITHM OF BINARY SEARCH
COMPLEXITY OF BINARY SEARCH
- Best Case Complexity : The best case complexity of linear search will be O(1) as the best case will be the one where the element is found at the middle position without further division of list.
- Worst Case Complexity : The worst case complexity of linear search will be O(log n).
- Average Case Complexity : The average case complexity of linear search will be O(log n) too.
ADVANTAGES OF BINARY SEARCH
Time Complexity of binary search is O(log n) which is less than time complexity of linear search which is O(n).
DISADVANTAGES OF BINARY SEARCH
- Sorted list is required to perform binary search. So, we have to sort the unsorted list in either ascending or descending order.
- There is a great loss of efficiency if the list does not support random access.
RVJ Learnings 