Comparative Study of Linear and Binary Search
Binary search is lots quicker than linear search. Some comparisons are following:
NUMBER OF ARRAY ELEMENTS EXAMINED
array size | linear search binary search
| (avg. case) (worst case)
--------------------------------------------------------
8 | 4 4
128 | 64 8
256 | 128 9
1000 | 500 11
100,000 | 50,000 18
A binary search on an array is O(log2 n) because at each test, you can "throw out" one half of the search space or array while a linear search in an array is O(n).
It is noteworthy that, for extremely small arrays a linear search can prove quicker than a binary search. Though, as the size of the array to be searched increases, the binary search is the clear winner in terms of many comparisons and therefore total speed.
Still, the binary search has some disadvantage. First, it needs that the data to be searched be in sorted order. If there is just one element out of order within the data being searched, it can throw off the entire process. While presented with a set of unsorted data, the efficient programmer has to decide whether to sort the data & apply a binary search or simply apply the less-efficient linear search. Is the cost of sorting the data is worth the raise in search speed gained along with the binary search? If you are searching only once, then it is possibly to better do a linear search in most cases.