Binary Search

Binary Search is an algorithm that is used for searching elements in a sorted array. A variation can also be used to search elements in a linked list as well. Its time complexity is O(log N) where N is the number of elements

Given below is a very simple implementation of Binary Search in Ruby

def binary_search(array, key)
    lower_bound = 0
    upper_bound = array.size - 1
    while lower_bound <= upper_bound
        mid = lower_bound + ( upper_bound - lower_bound ) / 2
        if array[mid] != key
            key < array[mid] ? upper_bound = mid - 1 : lower_bound = mid + 1
        else
            return mid
        end
    end
    return -1
end

key = 3
array = [1,2,3,4,5]
puts "Key #{key} is in #{array} at index #{binary_search(array, key)}"