Linear vs. binary search

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 Psedocode
While  (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(log \space n)$. However, the prerequisite for a binary search to work is that the array must be sorted.

/// Binary Search Pseudocode
left = 0
right = length(list) - 1
while (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])

Both searches hold different advantages and disadvantages depending on the nature of the data set. We can identify the major differences as follows:

• Implementation: Linear search can be implemented on any linear data structure. Binary search requires data structures with two-way traversal.
• Sorted Data: Linear search has no requirement for the data to be sorted. Binary search can only be implemented on sorted data.
• Efficiency: Binary search is faster (in terms of scan cycles) and more efficient compared to linear search especially for larger data sets.