module Ms::Support::BinarySearch

A binary search library adapted from: 0xcc.net/ruby-bsearch/


Ruby/Bsearch - a binary search library for Ruby.

Copyright © 2001 Satoru Takabayashi <satoru@namazu.org>

All rights reserved.
This is free software with ABSOLUTELY NO WARRANTY.

You can redistribute it and/or modify it under the terms of the Ruby’s licence.

Example:

% irb -r ./bsearch.rb
>> %w(a b c c c d e f).bsearch_first {|x| x <=> "c"}
=> 2
>> %w(a b c c c d e f).bsearch_last {|x| x <=> "c"}
=> 4
>> %w(a b c e f).bsearch_first {|x| x <=> "c"}
=> 2
>> %w(a b e f).bsearch_first {|x| x <=> "c"}
=> nil
>> %w(a b e f).bsearch_last {|x| x <=> "c"}
=> nil
>> %w(a b e f).bsearch_lower_boundary {|x| x <=> "c"}
=> 2
>> %w(a b e f).bsearch_upper_boundary {|x| x <=> "c"}
=> 2
>> %w(a b c c c d e f).bsearch_range {|x| x <=> "c"}
=> 2...5
>> %w(a b c d e f).bsearch_range {|x| x <=> "c"}
=> 2...3
>> %w(a b d e f).bsearch_range {|x| x <=> "c"}
=> 2...2

The binary search algorithm is extracted from Jon Bentley’s Programming Pearls 2nd ed. p.93

Constants

VERSION

Public Instance Methods

search_first(array, range=nil) { |array| ... } click to toggle source

This method searches the FIRST occurrence which satisfies a condition given by a block in binary fashion and return the index of the first occurrence. Return nil if not found.

# File lib/ms/support/binary_search.rb, line 72
def search_first(array, range=nil, &block)
  boundary = search_lower_boundary(array, range, &block)
  if boundary >= array.length || yield(array[boundary]) != 0
    return nil
  else 
    return boundary
  end
end
search_last(array, range=nil) { |array| ... } click to toggle source

This method searches the LAST occurrence which satisfies a condition given by a block in binary fashion and return the index of the last occurrence. Return nil if not found.

# File lib/ms/support/binary_search.rb, line 105
def search_last(array, range=nil, &block)
  # `- 1' for canceling `lower + 1' in bsearch_upper_boundary.
  boundary = search_upper_boundary(array, range, &block) - 1

  if (boundary <= -1 || yield(array[boundary]) != 0)
    return nil
  else
    return boundary
  end
end
search_lower_boundary(array, range=nil) { |array| ... } click to toggle source

Return the lower boundary. (inside)

# File lib/ms/support/binary_search.rb, line 51
def search_lower_boundary(array, range=nil, &block)
  range = 0 ... array.length if range == nil
  
  lower  = range.first() -1
  upper = if range.exclude_end? then range.last else range.last + 1 end
  while lower + 1 != upper
    mid = ((lower + upper) / 2).to_i # for working with mathn.rb (Rational)
    if yield(array[mid]) < 0
      lower = mid
    else 
      upper = mid
    end
  end
  return upper
end
search_range(array, range=nil, &block) click to toggle source

Return the search result as a Range object.

# File lib/ms/support/binary_search.rb, line 119
def search_range(array, range=nil, &block)
  lower = search_lower_boundary(array, range, &block)
  upper = search_upper_boundary(array, range, &block)
  return lower ... upper
end
search_upper_boundary(array, range=nil) { |array| ... } click to toggle source

Return the upper boundary. (outside)

# File lib/ms/support/binary_search.rb, line 84
def search_upper_boundary(array, range=nil, &block)
  range = 0 ... array.length if range == nil
          
  lower  = range.first() -1
  upper = if range.exclude_end? then range.last else range.last + 1 end
  while lower + 1 != upper
    mid = ((lower + upper) / 2).to_i # for working with mathn.rb (Rational)
    if yield(array[mid]) <= 0
      lower = mid
    else 
      upper = mid
    end
  end
  return lower + 1 # outside of the matching range.
end