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

Ace the Technical Interview

  • Easily find the gaps in your knowledge
  • Get customized lessons based on where you are
  • Take consistent action everyday
  • Builtin accountability to keep you on track
  • You will solve bigger problems over time
  • Get the job of your dreams

Take the 30 Day Coding Skills Challenge

Gain confidence to attend the interview

No spam ever. Unsubscribe anytime.