# 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.