Difference Between Linear Search and Binary Search

Linear search and binary search are the two methods which are used in arrays for searching the elements. Searching is a process of finding an element within the list of elements stored in any order or randomly.

The major difference between linear search and binary search is that binary search takes less time to search an element from the sorted list of elements. So it is inferred that efficiency of binary search method is greater than linear search.

Another difference between the two is that there is a prerequisite for the binary search, i.e., the elements must be sorted while in linear search there is no such prerequisite. Although both the searching methods use different techniques which are discussed below.

Content: Linear Search Vs Binary Search

1. Comparison Chart
2. Definition
3. Key Differences
4. Conclusion

Comparison Chart

Basis for comparison	Linear search	Binary search
Time Complexity	O(N)	O(log 2 N)
Best case time	First Element O(1)	Center Element O(1)
Prerequisite for an array	No required	Array must be in sorted order
Worst case for N number of elements	N comparisons are required	Can conclude after only log2N comparisons
Can be implemented on	Array and Linked list	Cannot be directly implemented on linked list
Insert operation	Easily inserted at the end of list	Require processing to insert at its proper place to maintain a sorted list.
Algorithm type	Iterative in nature	Divide and conquer in nature
Usefulness	Easy to use and no need for any ordered elements.	Anyhow tricky algorithm and elements should be organized in order.
Lines of Code	Less	More

Definition of Linear Search

In a linear search, each element of an array is retrieved one by one in a logical order and checked whether it is desired element or not. A search will be unsuccessful if all the elements are accessed, and the desired element is not found. In the worst case, the number of an average case we may have to scan half of the size of the array (n/2).

Therefore linear search can be defined as the technique which traverses the array sequentially to locate the given item. The program given below illustrates the searching of an element of the array using search.

Efficiency of linear search

The time consumption or the number of comparisons made in searching a record in a search table determines the efficiency of the technique. If the desired record is present in the first position of the search table, then only one comparison is made. When the desired record is the last one, then n comparisons have to be made.

If the record is to present somewhere in the search table, on an average, the number of comparisons will be (n+1/2). The worst case efficiency of this technique is O(n) stands for the order of execution.

C Program to search an element with linear search technique.

#include<stdio.h>
#include<conio.h>
void main()
{
int a[100], n, i, item, loc=-1;
clrscr();
printf("\nEnter the number of element :");
scanf("%d", &n);
printf("Enter the numbers : \n");
for(i=0;i<=n-1;i++)
 {
  scanf("%d", &a[i]);
 }
printf("\nEnter the number to be searched :");
scanf("%d", &item);
for(i=0;i<=n-1;i++)
{
  if(item == a[i])
  {
   loc = i;
   break;
  }
}
if(loc>=0)
 {
  printf("\n%d is found in position %d :", item, loc+1);
 }
else
 {
  printf("\n Item does not exist");
 }
getch();
}

Definition of Binary Search

Binary search is an extremely efficient algorithm. This search technique consume less time in searching the given item in minimum possible comparisons. To do the binary search, first, we have to sort the array elements.

The logic behind this technique is given below:

• First, find the middle element of the array.
• The middle element of the array is compared to the element to be searched.

There are three cases could arise:

1. If the element is the required element, then the search is successful.
2. When the element is less than the desired item, then search only the first half of the array.
3. If it is greater than the desired element, then search in the second half of the array.

Repeat the same steps until an element is found or exhausts in the search area. In this algorithm, every time search area is reducing. Therefore the number of comparisons is at most log (N+1). As a result, it is an efficient algorithm when compared to linear search, but the array has to be sorted before doing the binary search.

C Program to find an element with binary search technique.

#include <stdio.h>
void main()
{
int i, beg, end, middle, n, search, array[100];
 printf("Enter the number of element\n");
scanf("%d",&n);
 printf("Enter the %d numbers\n", n);
 for (i = 0; i < n; i++)
scanf("%d",&array[i]);
printf("Enter number to be searched\n");
scanf("%d", &search);
beg = 0;
end = n - 1;
middle = (beg+end)/2;
while (beg <= end) 
{
if (array[middle] < search)
beg = middle + 1; 
else if (array[middle] == search) 
{
printf("Search is successful.\n%d found at location %d.\n", search, middle+1);
break;
}
else
end = middle - 1;
middle = (beg + end)/2;
}
if (beg > end)
printf("Search is unsuccessful! %d isn't present in the list.\n", search);
getch(); 
}

Conclusion

Both linear and binary search algorithms can be useful depending on the application. When an array is the data structure and elements are arranged in sorted order, then binary search is preferred for quick searching. If linked list is the data structure regardless how the elements are arranged, linear search is adopted due to unavailability of direct implementation of binary search algorithm.

The typical Binary search algorithm cannot be employed to linked list because linked list is dynamic in nature and it is not known where the middle element is actually assigned. Hence, there is a requirement to design the variation of the binary search algorithm that can work on linked list too because the binary search is faster in execution than a linear search.