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.