[ruby-dev:14500] Re: Ruby/Bsearch

Tanaka Akira <[e-mail]> wrote:

>という 3つに分割できる場合、
>  a < b のときには a..(b-1) を返し、
>  a >= b のときには nil を返すわけですが、
>これを a < b か a >= b かにかかわらず a...b を返すようにするというのは
>いかがでしょう?

こんなもんすかね。

  % irb -r ./bsearch.rb
  >> %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

これはなかなかいいかも。


>ついでに bsearch_first や bsearch_last でも常に a や b - 1 を返すとい
>うのは... まぁこれはやりすぎか。

上の bsearch_range の挙動を実現するために
bsearch_first_boundary, bsearch_last_boundary を追加しました。
マニア向けですね。

--
高林 哲 (Takabayashi, Satoru)
http://namazu.org/~satoru/

#
# Ruby/Bsearch - a binary search library for Ruby.
#
# Copyright (C) 2001 Satoru Takabayashi <[e-mail]>
#     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_first_boundary {|x| x <=> "c"}
#  => 2
#  >> %w(a b e f).bsearch_last_boundary {|x| x <=> "c"}
#  => 1
#  >> %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

module Bsearch
  VERSION = '1.2'
end

class Array
  # 
  # The binary search algorithm is extracted from Jon Bentley's
  # Programming Pearls 2nd ed. p.93
  #

  #
  # Return the lower boundary. (inside)
  #
  def bsearch_first_boundary (range = 0 ... self.length)
    low  = range.first() -1
    high = if range.exclude_end? then range.last else range.last + 1 end
    while low + 1 != high
      mid = (low + high) / 2
      if yield(self[mid]) < 0
	low = mid
      else 
	high = mid
      end
    end
    return high
  end

  #
  # 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.
  #
  def bsearch_first (range = 0 ... self.length)
    boundary = bsearch_first_boundary(range)
    if boundary >= self.length || yield(self[boundary]) != 0
      return nil
    else 
      return boundary
    end
  end

  alias bsearch bsearch_first

  #
  # Return the upper boundary. (inside)
  #
  def bsearch_last_boundary (range = 0 ... self.length)
    low  = range.first() -1
    high = if range.exclude_end? then range.last else range.last + 1 end
    while low + 1 != high
      mid = (low + high) / 2
      if yield(self[mid]) <= 0
	low = mid
      else 
	high = mid
      end
    end
    return low
  end

  #
  # This method searches the LAST 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.
  #
  def bsearch_last (range = 0 ... self.length)
    boundary = bsearch_last_boundary(range)
    if (boundary <= -1 || yield(self[boundary]) != 0)
      return nil
    else
      return boundary
    end
  end

  #
  # Return the search result as a Range object.
  #
  def bsearch_range (range = 0 ... self.length)
    first = bsearch_first_boundary(range)
    last  = bsearch_last_boundary(range)
    return first ... last + 1
  end
end