Module: Bsearch

Defined in:
lib/bsearch.rb

Overview

Ruby/Bsearch - a binary search library for Ruby.

Copyright © 2001 Satoru Takabayashi <[email protected]>

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

Instance Method Summary collapse

Instance Method Details

#bfind(range = 0 ... self.length, &block) ⇒ Object 



118
119
120
121
122
 
# File 'lib/bsearch.rb', line 118

def bfind(range = 0 ... self.length, &block)
  pos = self.bsearch(range, &block)
  return nil if pos.nil?
  self[pos]
end

#bsearch_first(range = 0 ... self.length, &block) ⇒ Object Also known as: bsearch

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.



65
66
67
68
69
70
71
72
 
# File 'lib/bsearch.rb', line 65

def bsearch_first (range = 0 ... self.length, &block)
  boundary = bsearch_lower_boundary(range, &block)
  if boundary >= self.length || yield(self[boundary]) != 0
    return nil
  else 
    return boundary
  end
end

#bsearch_last(range = 0 ... self.length, &block) ⇒ Object

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.



98
99
100
101
102
103
104
105
106
107
 
# File 'lib/bsearch.rb', line 98

def bsearch_last (range = 0 ... self.length, &block)
  # `- 1' for canceling `lower + 1' in bsearch_upper_boundary.
  boundary = bsearch_upper_boundary(range, &block) - 1

  if (boundary <= -1 || yield(self[boundary]) != 0)
    return nil
  else
    return boundary
  end
end

#bsearch_lower_boundary(range = 0 ... self.length, &block) ⇒ Object

Return the lower boundary. (inside)



46
47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/bsearch.rb', line 46

def bsearch_lower_boundary (range = 0 ... self.length, &block)
  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(self[mid]) < 0
	lower = mid
    else 
	upper = mid
    end
  end
  return upper
end

#bsearch_range(range = 0 ... self.length, &block) ⇒ Object

Return the search result as a Range object.



112
113
114
115
116
 
# File 'lib/bsearch.rb', line 112

def bsearch_range (range = 0 ... self.length, &block)
  lower = bsearch_lower_boundary(range, &block)
  upper = bsearch_upper_boundary(range, &block)
  return lower ... upper
end

#bsearch_upper_boundary(range = 0 ... self.length, &block) ⇒ Object

Return the upper boundary. (outside)



79
80
81
82
83
84
85
86
87
88
89
90
91
 
# File 'lib/bsearch.rb', line 79

def bsearch_upper_boundary (range = 0 ... self.length, &block)
  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(self[mid]) <= 0
	lower = mid
    else 
	upper = mid
    end
  end
  return lower + 1 # outside of the matching range.
end