Linear and binary searches are algorithms used to find a specific element from a linear data set (such as an array, linked list, etc.) The algorithms only differ in the methodology employed to find the desired element. Before understanding the differences, let us look at each search individually.
Linear search
A linear search scans each element of the array sequentially until the required element is identified. As a result, the worst time complexity is of the order O(n) since the time required to search an element is proportional to the number of the elements.
/// Linear Search PsedocodeWhile (element_found = False and counter < Length(List)) If (list[counter] = element_required) element_found = true Display (list[counter]) Else counter = counter + 1 if (counter = Length(list) + 1) Display ('Element not found')Binary search
A binary search finds the required element in an array via middle element value comparison; hence, cutting the array length to be searched in each scan cycle by half. This leads to faster computation and reduces the worst time complexity to O(logn). However, the prerequisite for a binary search to work is that the array must be sorted.
/// Binary Search Pseudocodeleft = 0right = length(list) - 1while (left <= right) counter = floor((left + right) / 2) if (list[counter] < element_ required) left = counter + 1 if (list[counter] > element_required) right = counter - 1 else Display(list[counter])