**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.