Comparison of Binary Search and Linear Search

A linear search scans one item at a time, without jumping to any item. we start at the first index of the array and then compare with the key. If the key is found in the array them search process successful.

1. The worst case complexity is O(n), some times known as O(n) search.
2. Time taken to search elements keep increasing as the number of elements increased.

A binary search however, cut down your search to half as soon as you find middle of a sorted list. The binary search is a recursive algorithm where every time we divide the array into two parts and decide from with direction we move until the desired element is found.

1. The middle element is looked to check of it is greater than or less than the value to be searched.
2. Accordingly, search is done to either half of the given list. 

 

Where Binary search is used in practice?

Binary search is used everywhere. Take any sorted collection from any language library (Java, .NET, C++ STL and so on) and they all will use (or have the option to use) binary search to find values

Binary search can be used to access ordered data quickly when memory space is tight.

Before the arrival of STL and .NET framework, etc, you rather often could bump into situations where you needed to roll your own customized collection classes. Whenever a sorted array would be a feasible place of storing the data, binary search would be the way of locating entries in that array.

Important Differences

• Input data needs to be sorted in binary search and not in linear search
• Linear search does the sequential access where as Binary search access data directly / randomly.
• Time complexity of linear search is O(n), Binary search has time complexity O(n)
• Linear search performs equality comparisons and binary search performs ordering comparisons

 Source:stackoverflow.com