Algorithms 101:

Linear vs Binary Search

What is the best way to search an array of information? In the world of computer science, there are many ways to approach this question. There is a significant probability that during an interview for a programming position an applicant will be presented with at least some algorithm question on a job interview.

When approaching an array of information, the most natural way to process the information is to do a linear search. This type of search can be efficient enough for small applications. However, when iterating over large pieces of information, this will hamstring an application. The indicator of the need for a linear search is when there is no correlation between the order of the array and the piece of information being searched for. If that sounds confusing, think of it this way; an array and inside the array are not simple values. There are strings, booleans hashes, integers, floats, null values, and so on. There is no way to determine the probability of any value being the preceding or subsequent value of the current value in this array. Suppose there is no possibility of reordering the array-based items upon the items’ relative value compared to one another. In that case, a linear search is appropriate. In that case, there is no way to determine with certainty that one value would proceed or follow a randomly selected value. An unsorted array is that one must search through the array item by item, comparing each to the search’s value.

Below the value desired is 9954. In a linear search, the items are evaluated starting at index 0 and increasing one index after each failed evaluation. In JS this may be given as a .filter() function.

def linear_search(array, key)
   array.index do |value|
        value == key
    end
end
linear_search([2, 22, 56, 5, 9954, 1], 9954)

An alternative to a linear search is a binary search. This search is valuable to save time in complex arrays that can be sorted by a particular value. For example, when given an array of 29 items, we have to run a linear search if it is unsorted. If it can begin as a sorted array of those same 29 items, one can begin with a binary search.

The short of it is that a binary search will divide the array into ‘halves’ — rounding down if the array is uneven in length. The search will then evaluate the ‘middle’ value selected and evaluate its item against the desired item. If the desired item is greater in value than the current item, then the first half of the array can be ignored because any item found within it will have a lesser value than the item being searched for. The process repeatedly continues until the item searched for is found or is determined not to be in the array.

If there is an item, we are searching for in a sorted array of 256 items. The particular item ‘x’ is found at the index of 243. When a linear search runs with this array, it will evaluate 243 items before it is found. When a binary search runs with this array, it will only need to search eight times to find ‘x.’

Below the value desired is 5. In a binary search, the items are sorted as a precondition. This search will halve the array over and over until it finds the desired value.

def binary_search(array, key)
    low = 0 //index start
    high = array.length-1 //index end
    while (low<=hi) //as long as this state persists run the below
        middle = low+((hi-low)/2) //setting the middle index
        if array[mid] == key //checking the value of the middle idx
            return a[mid]
        elsif array[middle] > key 
            high=middle-1 //reassign high variable
        else
            low=middle+1 //reassign low variable
        end
    end
    return "Not Found in Array" //if the value is not present
end
//then run the method with the code below
binary_search((1..7).to_a, 5)

First: Takes the total length and splits it into two parts, +> then evaluates the value in the largest index of the lower half against the desired ‘5’ => 4== 5 => false, => 4> 5 so the value cannot be in any index lower than 3…

Then: Takes the new length and splits it into two parts, => then evaluates the value in the largest index of the lower half against the desired ‘5’, => 6 == 5 => false, => 6 > 5 => true, so the value cannot be higher than 5…

Then: Takes the new length and splits it into two parts, => then evaluates the value in the largest index of the lower half against the desired ‘5’, => 5 == 5 => true. See below for the variable changes.

The program exits and we are done with our binary search function in only three quick evaluations instead of five. As the array grows, this process becomes more valuable. If it is possible, instead of running a sort on the front end, rather, each time something is saved into the database it could be beneficial to save sorted arrays that are easily accessible to the user when running binary searches.