LINEAR AND BINARY SEARCH
In this article we will discuss the main searching algorithms: linear search and binary search. The aim of searching algorithms is to find a given item in an array. The array can be sorted or unsorted as well. As usual, both algorithms have some advantages as well as some disadvantages.
The aim of linear search is to find a given item in an unsorted array. This is the case usually, so the array is unsorted. In this case we have to iterate through the array and consider every single item on a one by one basis. This is why linear search has O(N) linear running time complexity.
So as you can see the code above, we have to consider every item in the array. If the array does not conatin the item we are looking for, we return -1. This linear search is the fundamental basis for selection sort.
So far, we have considered linear search. Can we do better? Yes, if the array is sorted. We are able to construct a search algorithm with O(logN) running time complexity, which is definitely better than O(N). Binary search begins by comparing the target value to the value of the middle element of the sorted array.
- if this element is greater than the item we are looking for: we continue the search in the left subarray
- otherwise we consider the right subarray
OK, why is it good? Because we discard half of the items on every iteration. Thats why we will end up with O(logN) logarithmic running time. This approach can be implemented easily with recursive method calls.