Linear Search vs. Binary Search

Have you ever lost a worksheet in your backpack? Many people use different approaches to finding items, whether it is in a backpack or a grocery store. Similar to our daily lives, computers also need to search quite frequently. Also similar to humans, a computer has different approaches to searching for an element. Two of the most popular methods are linear and binary search. Linear and binary search algorithms find a specific element from a linear data set, like an array.

Linear search scans each element sequentially until the computer identifies the intended element or searches the entire data set. Linear search’s disadvantage is the time complexity. Because linear search scans each element starting from the beginning, it is highly inefficient. The graph for linear search would model y = n.

Meanwhile, binary search finds elements by starting at the midpoint of the data set for each comparison. Like linear search, binary search repeats until the computer finds the intended element or examines the entire data set. The graph for binary search models y = log(n). However, a prerequisite for binary search is that the data set must be in order. Depending on the situation, this could mean alphabetical order, numerical order, or generally some order. This prerequisite is often demanding, hence linear search may be a better alternative.

Efficiency, the number of steps needed to complete an algorithm, is used to measure linear and binary search. Binary search is more efficient for sorted data sets, especially with large data sets. Therefore, to determine which search algorithm is better, the situation needs to be closely examined as both options have advantages and disadvantages. 

The average search times graphed for both linear and binary search.

Source: code.org