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 haystack[cur] end end
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.