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 binary search method is more efficient 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 | Somehow tricky algorithm and elements must be arranged in order |

Lines of Code | Less | More |

### Definition of Linear Search

In a linear search, we access each element of an array one by one sequentially and see 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. If 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 using 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); print("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.
- Compare the middle element of the array to the element to be searched.

There are three cases could arise :

- If the element is the desired element, then the search is successful.
- If 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 search an element using binary search technique.

#include<stdio.h> #include<conio.h> void main() { int a[100], n, i, item, loc, mid, beg, end, n, flag=0; clrscr(); printf("\nEnter the number of element :"); scanf("%d", &n); print("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); loc = 0; beg = 0 ; end = n-1; while((beg <= end) && (item ! = a[mid])) { mid = ((beg+end) / 2); if(item == a[mid]) { printf(" Search is successful \n"); loc = mid; printf(" Position of the item is %d :", loc+1"); flag = flag+1; } else if (item < a[mid]) end = mid-1; else beg = mid+1; } if(flag == 0) { printf("Search is unsuccessful\n", item, loc+1"); } 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. If an array is the data structure and elements are organized in sorted order, then binary search is preferred for **fast** searching. If linked list is the data structure no matter how the elements are arranged, linear search is preferred due to unavailability of direct implementation of binary search algorithm.

The original Binary search algorithm can not be applied to linked list because linked list is dynamic in nature and it is not known where the middle element is actually allocated. He, 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.

## Leave a Reply