Binary Search in Ruby

I was reading the source code of ipcat gem. It is a ruby port of the ipcat library to classify IP addresses from known datacenters. This gem is useful to filter out malicious traffic. If the IP address is some hosting company, it is most likely a malicious user. The end of the ipcat.rb uses binary search algorithm to find the needle in haystack:

# Assume ranges is an array of comparable objects
def bsearch(needle, haystack = ranges, first = 0, last = ranges.size - 1)
  return nil if last < first # not found, or empty range

  cur = first + (last - first) / 2
  case haystack[cur] <=> needle
  when -1 # needle is larger than cur value
    bsearch(needle, haystack, cur + 1, last)
  when 1 # needle is smaller than cur value
    bsearch(needle, haystack, first, cur - 1)
  when 0

Binary search is a fast search algorithm. It uses divide and conquer strategy. The data must be in sorted form. It looks for a given item by comparing the middle most item of the collection. If the middle item is greater than the item, we search in the subarray to the left of the middle item. This process continues until the size of the subarray becomes zero.

Related Articles

Create your own user feedback survey