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

### Comparison Chart

Basis for comparison | Linear search | Binary search |
---|---|---|

Time Complexity | O(N) | O(log 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 log N 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 :

- If the element is the required element, then the search is successful.
- When the element is less than the desired item, then search only the first half of the array.
- 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(); }

## Key Differences Between Linear Search and Binary Search

- Linear search is iterative in nature and uses sequential approach. On the other hand, Binary search implements divide and conquer approach.
- The time complexity of linear search is O(N) while binary search has O(log
_{2}N). - The best case time in linear search is for the first element i.e., O(1). As against, in binary search, it is for the middle element, i.e., O(1).
- In the linear search, worst case for searching an element is N number of comparison. In contrast, it is log
_{2}N number of comparison for binary search. - Linear search can be implemented in an array as well as in linked list whereas binary search can not be implemented directly on linked list.
- As we know Binary search requires the sorted array that is reason It requires processing to insert at its proper place to maintain a sorted list. On the contrary linear search does not require sorted elements, so elements are easily inserted at the end of the list.
- Linear search is easy to use, and there is no need for any ordered elements. On the other hand, Binary search algorithm is however tricky, and elements are necessarily arranged in order.

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

Navjot Kaur says

Helps a lot.

Explained perfectly and in an easy way.

Good job.

Keep it up.

God bless you.

HARSHIL says

Thanks for the explanation

Shreya says

Thanks, it helped a lot!

Shreya says

Thanx it helped a lot!

Venkat says

nice article