Binary search

Binary search is a fantastic algorithm for finding elements in an ordered list (or array) of items. It works by repeatedly dividing the search space in half. It starts with a middle element and compares it against your key. If the search value is smaller than the middle element, algorithm skips the second part of an array.

The process repeats until the algorithm gets the right value. It’s crucial that the array is already sorted for this algorithm to work.

Given the search space is halfed every iteration, Big O and the worst case scenario is O(log n) where n is the total number of elements. Algorithm doesn’t depend on the number of elements so the space complexity is O(1).

Binary search works the same for almost all inputs and the only different parameter is the search space so it should be fairly easy to make both recursive and iterative solutions.

Iterative version written in Ruby:

def binary_search_iterative(arr, val)
  left, right = [0, arr.length - 1]
  while left < right
    mid = (left + right) / 2
    if arr[mid] == val
      return mid
    elsif arr[mid] < val
      left = mid + 1
    else
      right = mid
    end
  end
  false
end

Recursive version written in Ruby:

def binary_search_recursive(arr, val)
  left, right = [0, arr.length - 1]
  if left >= right
    return false
  end
  mid = (left + right) / 2
  if arr[mid] == val
    mid
  elsif arr[mid] < val
    binary_search_recursive(arr[(mid+1)..right], val)
  else
    binary_search_recursive(arr[left..mid], val)
  end
end

Test inputs:

test_inputs = 10.times.map { rand(100) }.sort
#=> [5, 7, 24, 47, 58, 59, 59, 77, 90, 97]

binary_search_iterative(test_inputs, 58)
#=> 4

binary_search_recursive(test_inputs, 58)
#=> 4

Also, Wikipedia has a great image which shows how the number 7 is found inside an array:

From Wikipedia: Visualization of the binary search algorithm where 7 is the target value