Search Algorithms

Question Click to View Answer

Write a sequential search algorithm that returns true if an item is included in a list and false otherwise.

The sequential search algorithm iterates over every element in a list to see if an item is included in the list.

def sequential_search(list, item)
  list.each do |i|
    return true if i == item
  end
  false
end

puts sequential_search([1, 5, 9], 9) # => true
puts sequential_search([1, 5, 9], 44) # => false

What is the Big O notation for the sequential_search algorithm?

The sequential_search algorithm's performance will vary depending on the position of the item in the list. If the item is in the first position of the list, the loop will only iterate one time. If the item is in the last position of the list or is not in the list at all, the loop will iterate list.length or n times. Big O analysis typically focuses on the worst case scenario so this algorithm is O(n) = n.

Write a method that uses the binary search algorithm to determine if an item is in a list.

Here is an overview of the binary search algorithm from Wikipedia: "The binary search algorithm begins by comparing the target value to the value of the middle element of the sorted array. If the target value is equal to the middle element's value, then the position is returned and the search is finished. If the target value is less than the middle element's value, then the search continues on the lower half of the array; or if the target value is greater than the middle element's value, then the search continues on the upper half of the array. This process continues, eliminating half of the elements, and comparing the target value to the value of the middle element of the remaining elements - until the target value is either found (and its associated element position is returned), or until the entire array has been searched (and "not found" is returned)."

def binary_search(list, item)
  first = 0
  last = list.length - 1
  while first <= last
    midpoint = (first + last) / 2
    if list[midpoint] == item
      return true
    else
      if item < list[midpoint]
        last = midpoint-1
      else
        first = midpoint+1
      end
    end
  end
  false
end

testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
binary_search(testlist, 13) # => true
binary_search(testlist, 15) # => false

Write the binary search algorithm recursively.

def binary_search(list, item)
  return false if list.length == 0
  midpoint = list.length / 2
  return true if list[midpoint] == item
  if item < list[midpoint]
    binary_search(list[0...midpoint],item)
  else
    binary_search(list[midpoint+1...-1],item)
  end
end

testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
binary_search(testlist, 3) # => false
binary_search(testlist, 13) # => true

What is the Big O performance of the binary search algorithm.

See this section for a detailed description of how to compute the performance of this algorithm. In short, the list is cut in half each iteration and this results in O(log(n)) performance.