Binary Search in Ruby

I just started reading Grokking Algorithms, by Aditya Bhargava, which has really user-friendly explanations of common programming algorithms.

One basic algorithm every programmer should know is binary search. Binary search is the most efficient way to search through an array of sorted data to find what you’re looking for. (It’s crucial that the data be sorted first.) Here are the steps:

(1) Compare the item you’re looking for to the median value of the array. If your item is the median, congrats, you’ve found it! Otherwise:

(2) If your item is higher than the median, chop off the lower half of the array (since it won’t be in there). If it’s lower, chop off the upper half.

(3) Go back to step 1, comparing the item with the median of the new, smaller array.

The nice thing about binary search is that its runtime is O(log n), i.e. logarithmic. If your array has 128 items, it will take at most 7 steps to find your item; double the array to 256 items, and you need only add one more step.

I decided to implement binary search in Ruby. My program accounts for the possibility that your item is not in the data. Here’s my program, assuming the data is already sorted:

def in_list?(item, array)
  median = array[array.length/2]
  if item == median
    return true
  elsif array.length == 1
    return false
  elsif item < median
    array = array[0...array.length/2]
    in_list?(item, array)
  elsif item > median
    array = array[array.length/2..-1]
    in_list?(item, array)
  end
end

If the array is not already sorted, it’s a little longer:

def in_list?(item, array)
  check(item, array.sort)
end

def check(item, array)
  median = array[array.length/2]
  if item == median
    return true
  elsif array.length == 1
    return false
  elsif item < median
    array = array[0...array.length/2]
    check(item, array)
  elsif item > median
    array = array[array.length/2..-1]
    check(item, array)
  end
end

That’s binary search.

Leave a Reply

Your email address will not be published. Required fields are marked *