Linear Search v/s Binary Search || Comparison and Algorithm of Linear and Binary Search

Consider a company with one thousand employees and each employee having a unique ID. In such a case we want to find all data about an employee OR consider another case where a hundred thousand students have appeared for a national level exam then in such a case if we want to search for a student by his roll number then we need very efficient search algorithm to give us fast results.

Here we have two search algorithms Linear Search and Binary Search.

So, let's start with linear search method first
This is the simplest search algorithms. 

The algorithm simply says that we will keep comparing with each element of array starting from first element till the last index of array

If we find the element exit program at that point and print element found at that particular index, else if we do not find element till the last index then print that element was not found

Eg. 
3, 6, 2, 1, 8, 4

Say we want to search for 2 in this array
We will compare with 3, 6, and 2 as we hit the element 2 we will print that  element was found at index 3

Say we want to search 7,

Algorithm will search from start to end and after reaching end it will print that element 7 was not found.
The algorithm goes this way
linear search in array A , n is the last index, e is element to be searched, is a variable for index


Step 1: Set i to 0
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit


Now lets understand binary search 
The algorithm is called binary search because it searches by dividing the algorithm into half repeatedly. Lets understand better with the algorithm. But before that let me mention that,

BINARY SEARCH METHOD IS USED ONLY FOR SORTED ARRAYS.


In this array (A) suppose we will take element to be searched in variable (ele)
We will consider two more variables called upper bound (ub), and lower bound (lb), 
ub = last index of array, lb = 0 (i.e., 1st index of array)


It will be easy to understand algorithm along with an example...


consider a sorted array 


0,1,2,3,4,5, 6,  7 <- index
1,3,4,6,7,9,11,15 <- elements


Say ele = 7,
ub = 7, lb = 8
We will find the mid index first using the formula mid = (ub + lb)/2


If A[mid] = ele, then print (element found at mid) and exit 
here our mid = (7+0)/2 = 3 
(our variable will be of int type so mid = 3, not 3.5) 
A[3] = 6 ≠ ele = 7,


Else if A[mid] < ele, 
  Now, As we know that our array is sorted and our element to be searched is greater than mid required search mist be done in the upper half of array, so we need to change values in our lower bound (lb) , and mid. Upper bound will be the same.


lb = mid + 1
mid = (lb + ub)/2
in our example 7 stored in ele > 6 in A[mid], so we need to check the upper half of array

In our example lb = 3+1= 4
mid = (4 + 7)/2 = 11/2 = 5 (not 5.5, as explained before)

there can be one more case where the ele < A[mid] ( i.e. element is in lower half)

So we need one more condition using Else if

Else if A[mid] > ele, 
its obvious in this case that we need to check lower half so, we need to change upper bound and mid.

ub = mid -1
mid = (lb+ub)/2

Having done with these conditional statements we need to again go to one of our previous steps and see if our A[mid] = ele, thus will be done using loop.

A[mid] = A[5] = 9
ele = 7
A[mid] = ele , this statement is FALSE so we will check the next condition as our algorithm goes, which is

A[mid] < ele, this is also FALSE in our case
Now checking A[mid] > ele, tbus is TRUE
Therefore ub = mid - 1 = 5 - 1 = 4
mid = (lb + ub)/2 = (4+4)/2 = 8/2 = 4

Now, loop check if A[mid] = A[4] = ele ?
as ele = 7 and A[mid] = 7, so our array finds the required element and exits from the algorithm 

The conditional statement we are declaring 
lb = mid + 1
And ub = mid - 1

for case where our element is absent from our array, there will be a time when ub will become less than lb so, in this condition we cam conclude that element is absent from array and exit from the algorithm

The condition statement we need to check for it is 
Else if lb > ub
  Print(Element not found)
  Exit from algorithm  

Lets write a statement algorithm for this 


1. Start
2. Take array A of size n
3. Take ele from user 
4. Declare and define lb = 0 ub = n-1

5. mid = (lb + ub)/2

6. if A[mid] = ele,
Then 
{
   Print("Element found at " mid) 
   go to step 10
}

7. if A[mid] < ele,
Then
{ 
   lb = mid+1
   mid = (lb + ub)/2
   go to step 6
}

8. if A[mid] > ele,
Then
{ 
   ub = mid-1
   mid = (lb + ub)/2
   go to step 6
}

9. if ub < lb,
Then,
{
Print("Element NOT found")
go to step 10
}

10. Exit

Now let's compare both algorithms according to their time complexity

Linear Search :-

In best case:-  It may find the element at the first position of array itself so its best case time complexity is O(1).

In worst case:- It may have to traverse the complete algorithm and still not be able to find element because it might be absent. In that case as the array will be of size (n)
So the time complexity will be O(n)

Binary Search :-

In best case:-In best case : It may find element at mid in the first time of iteration only. So it will complete the search in O(1) time complexity.

In worst case:- It the algorithm will keep dividing the array into half during every iteration and reduce the size of n, n/2, n/4, n/8, n/16 and so on up-to the ub < lb. 

In this case algorithm will get executed in O(log(n)) time complexity.

Comparing for arrays of large input size we can conclude that Binary search having rime complexity O(log(n)) is far better than linear search of time complexity O(n) in the worst case.

Click here to go to the link where we have code for both algorithms in C language.

Till then #KeepLearningKeepGrowing