Binary Search Algorithm
Brief Information
It is a searching algorithm which is used for finding the position of required value or
data within a sorted array. Indeed, it is much faster in comparison to linear search. Firstly, for using
a binary search algorithm in an array or linked list, it must be sorted . And, this sorting
process can be done by using any kind of sorting algorithm like selection sort and
merge sort.
Working Mechanism
Binary sorting algorithm can be used only in sorted array. Moreover, this searching algorithm
reduces the time complexity to 0 (Logn). Basically, after first comparison, half of the
elements of an array are ignored. The algorithm for this searching method occurs
recursively until required value is found in the array.
Here, the whole mechanism of binary searching algorithm is explained through different
steps. Let ‘x’ be the data which is to be searched in the given array or linked list.
Step 1:
First, ‘x’ is compared with the middle element of the array or linked list.
Step 2:
If ‘x’ matches with the middle element, then the mid index is returned.
Step 3:
If ‘x’ is greater than the middle element, then we know that ‘x’ lies on the right
side of the middle index. So, the left part of the middle index is completely ignored,
and the above steps recursively takes place.
Step 4:
But if ‘x’ is less than the middle element then we know that ‘x’ lies on the left
side of the middle index. So, the right part of the middle index is completely ignored,
and the above steps recursively takes place.
For Example:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
| Search 20 | 10 | 20 | 30 | 40 | 50 | 60 | 70 | |
| l=0 | 1 | 2 | m=3 | 4 | 5 | h=6 | ||
| 20<40, take 1st half | 10 | 20 | 30 | 40 | 50 | 60 | 70 | |
| l=0 | m=1 | h=2 | 3 | 4 | 5 | 6 | ||
| Found 20, return 1 | 10 | 20 | 30 | 40 | 50 | 60 | 70 | |
Let us consider an array of sorted number as shown above where number “20” is to
be searched.
At first highest index (let be h) and lowest index (let be l) is calculated and the mid
index of the array (let be m) is calculated by the formula m = (l + h)/2. In the above
example, l=0 and h=6. So, m = (0+6)/2 i.e. 3. The element of the third index i.e.40 is
compared with the searched number i.e. 20. Since 20 is less than 40, the number 40
and right to 40 are ignored. Now 20 is searched among the remaining numbers i.e.
[10,20,30]. For this array, l=0 and h=2. So, m = (0 + 2)/2 i.e. 1. Now, the element of
the first index i.e. 20 is compared with searched number i.e. 20. Since these two
numbers matched, its index i.e. 1 is returned.
Linear Search Algorithm
Brief Information
It is the most simple and basic search algorithm in which we search an element or
value in a given array or linked list by checking that element from the starting, till the
desired element or value is found. Since the required value is searched by comparing
with every element in the array, there is no need to sort the array. The average time
complexity of linear search is given by 0(n). Although it is the most basic and simple
searching algorithm, it is rarely used in comparison to binary search as binary search
is significantly faster than linear search.
Working Mechanism
The working mechanism of linear search is very simple. It can be explained in the
following steps:
• Searching for the element starts from the leftmost element of the array or linked
list and the value to be searched is compared one by one with each element of
that array.
• If the searched element matched with an element of that array, then the index
of that element is returned.
• If the searched element does not match with any of elements, -1 is returned.
For Example:
Finding 15 in given array.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 10 | 30 | 20 | 50 | 40 | 15 | 32 |
Let us consider, we have to search the number 15 by using linear search algorithm in
an unsorted array as shown in the above figure. In linear search, the item to be
searched is continuously compared with each element of the array. So, at first “15” is
compared with “10”.
If the searched item does not match with the element, then second
element of array is compared with the searched item. In the above figure, 15 is
compared with every element until fourth index. On comparing with the fifth index of
the array, the searched element matches with the element of the array and the index
of that element i.e. 5 is returned.
