Algorithms play a vital role in the field of Computer Science. In fact, it is an indispensable part. An idea that can be represented step by step how to solve a particular problem is an algorithm. An algorithm is what we later formulate into codes. So, here we will be looking at the most simplest of these algorithms, namely the search algorithms.
Let us say I am given an array:
3 6 1 24 10 18 5 8 33 55 (n=10)
The element I am searching for is ‘10’.
The first approach that most of us might take is that, we will check on throughout the array and compare to see if my element matches with any element in the array, till I find the array or till the end of the array in case if the element is not at all present in the array. This is exactly the Linear Search algorithm.
So here, I go through the array, checking 3, 6, 1, 24 and finally 10. Here 10 matches and I can now return it.
- for i <- 1 to n
- do if A[i] = x
- then return i
- else i <- i + 1
- return “x not found”
This algorithm takes about O(n) time for execution, where n is the size of the array.
If the array that I am searching in is sorted, would that have been an advantage? If I am to follow the same Linear Search, it wouldn’t make any difference. But we can actually do it in a better way and reduce the time complexity. Let us see how. Here is where the Binary Search algorithm comes in place.
Suppose we have the array
1 2 3 4 5 6 7 8 9 10 (n = 10)
The element I am searching for is ‘6’.
So first I take the middle element or the n/2th element, here, it is ‘5’.
I check if 6 is equal to 5. Of course not and I also find that 6 is greater than the middle element.
So now I can be sure that the element I am searching for will obviously be in the 2nd half of the array, as it is an ascendingly sorted array.
The array that I consider now becomes
6 7 8 9 10 (n = 5)
Again, I check the middle element 8, compares it with 6, to find that the element I am searching for is now less than the middle element. So, the element would be in the first half of the array. So the array that I consider now, reduces to
6 7 ( n = 2 )
Here, again I check the n/2th element, which is ‘6’ here, and finds it to be equal to the element I am searching for. Now I can return the same.
- low <- 1
- high <- n
- while low <= high
- do mid <- (low + high)/2
if A[mid] = x
then return mid
elseif A[mid] < x
then low <- mid + 1
else high <- mid − 1
5. return “x not found”
The above algorithm takes only O(log n) time for its completion, as n is halved at each step and hence, it is a better algorithm than Linear search in case of sorted array.