Linear Search vs Binary Search
Linear Search
As a beginner programmer, conducting a linear search on an array is conceptually simple and straight-forward to implement. Let’s take a look at an arbitrary example code below. The code is written in Ruby, but the concept of a linear search is language-agnostic.
arr = [1, 2, 3, 4, 5, 6, 7, 8, 11]def linear_search(arr, val)
arr.each do |n|
return true if n == val
end false
endlinear_search(arr, 3) # returns true
linear_search(arr, 9) # returns false
Our first invocation of linear_search searches for the integer 3; next we search for 9. The search behavior is the same — we iterate through the elements of the array sequentially in order to determine whether or not there is a match. If a match is found, the method immediately returns true. If the element being searched for is not in the array, the code will iterate through and compare every element of the array.
In this simple example, the maximum number of iterations (nine) is negligible. But imagine that we are searching an array with hundreds or thousands of elements. On average, the number of comparisons a linear search must perform before finding a match in the array (assuming there is a match at all) is about half of the search array’s size. Performing five comparisons while searching an array of ten elements is insignificant; performing 5,000 comparisons while searching an array of 10,000 elements is a different story. If there is no match, a linear search of such an array would require 10,000 comparisons. Linear searches are inefficient.
Binary Search
The binary search is a more efficient way to search an array, but there is one important caveat: the array on which you perform a binary search must be in order. A linear search can be performed on an array with its elements in any order.
In the below code sample, we use abinary_search method to search an ordered array containing 25 integers using the binary search algorithm. Again, this is a very simple example and the language in which the code is written (Ruby) is unimportant.
arr = [1, 2, 3, 4, 5, 9, 11, 13, 15, 18, 32, 33, 34,
35, 38, 40, 41, 42, 43, 58, 60, 62, 68, 80, 82]def binary_search(arr, val)
startIdx = 0
endIdx = arr.size - 1 while (startIdx <= endIdx) do
midIdx = (startIdx + endIdx) / 2 if arr[midIdx] == val
return true
elsif arr[midIdx] > val
endIdx = midIdx - 1
else
startIdx = midIdx + 1
end
end false
endbinary_search(arr, 11) # returns true
binary_search(arr, 99) # returns false
The binary search algorithm works by first inspecting the array’s middle element. If the element is not a match, the program determines whether the current element is less-than or greater-than the search value and proceeds by next inspecting the middle element of either the first or last half of the array. The program continues to halve the array and compare the new ‘middle’ element to the search value until either a match is found or there are no more elements to test.
For reference, here are the portions of the array utilized on each iteration of the while loop in the code above when we invoke binary_search with our test case of 99 , which is not an element in the array.
# first iteration (original array)
[1, 2, 3, 4, 5, 9, 11, 13, 15, 18, 32, 33, 34, 35, 38, 40, 41, 42, 43, 58, 60, 62, 68, 80, 82]# second iteration
[35, 38, 40, 41, 42, 43, 58, 60, 62, 68, 80, 82]# third iteration
[58, 60, 62, 68, 80, 82]# fourth iteration
[68, 80, 82]# fifth iteration
[82]# no more elements; returns false
Notice that for this array of 25 elements, the max number of comparisons is 5. The maximum number of comparisons of a binary search can be calculated simply. It is the smallest power of 2 that is larger than the size of the array. The smallest power of 2 larger than our example array, arr , is 2⁵, which is equal to 32. Think back to the hypothetical 10,000 element array we imagined when learning about linear searches. 2¹⁴ = 16,384 and is the smallest power of 2 larger than 10,000. Thus, we can surmise that the max number of comparisons to be made on a 10,000 is 14. Compare that to a maximum of 10,000 comparisons and an average of 5,000 comparisons when using a linear search, and the marked difference in efficiency is clear.
When searching small sets of data, the algorithm used may not be of great consequence. A linear search is simple, easy to implement, and can search an array in any order. However, as the amount of data you are working with grows, consider alternate approaches that are more efficient. The binary search algorithm is a good option when working with large, sorted arrays.
