ruby-dev

Tanaka Akira <akr@m17n.org> 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 <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_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

Thread

Prev Next

In This Thread

Prev Next

[#14185] ruby on Linux/m68k — akira yamada / やまだあきら <akira@...>

[#14195] exception at IO.popen failure — nobu.nakada@...

[#14196] fork() on MacOS — nobu.nakada@...

[#14206] undef_method :method_missing — Kenichi Komiya <kom@...1.accsnet.ne.jp>

[#14229] [BUG] segv on [str].pack("p") — Koji Arai <JCA02266@...>

[#14300] 名前空間を調べる効果的な方法はありますか？ — 西 啓一朗 <receiver@...>

[#14327] Re: [ruby-cvs] ruby/ext/socket: * string.c (rb_str_lstrip_bang): new method. — "U.Nakamura" <usa@...>

[#14338] setup.rb (Re: Common GUI framework) — Minero Aoki <aamine@...>

[#14382] [BUG] segv on regex matching with long string — TAKAHASHI Masayoshi <maki@...>

[#14390] [Patch] pp.rb and debug.rb — "NAKAMURA, Hiroshi" <nakahiro@...>

[#14406] typo in ruby 1.7 — Koji Arai <JCA02266@...>

[#14413] 1.7.1 2001-08-06: if true && /match/ — WATANABE Tetsuya <tetsu@...>

[#14430] Re: [ruby-cvs] ruby: * object.c (rb_obj_inspect): merge from 1.7: remove useless space. — Kazuhiro NISHIYAMA <zn@...>

[#14436] 1.7.1 2001-08-06: [BUG] unknown node type 0 — akira yamada / やまだあきら <akira@...>

[#14441] "foo".lstrip! should return `nil'. — Koji Arai <JCA02266@...>

[#14445] string.c rb_str_cmp() — TOYOFUKU Chikanobu <toyofuku@...>

[#14464] Ruby/Bsearch — akira yamada / やまだあきら <akira@...>

[#14465] Ruby/Bsearch — akira yamada / やまだあきら <akira@...>

[#14480] avoid compile warning of tcltklib with VC5 — "U.Nakamura" <usa@...>

[#14505] BUG: ruby 1.6.4 cannot use threads on Sparc (segv) — akira yamada / やまだあきら <akira@...>

[#14516] ext/digest/sha2/extconf.rb and try_run — WATANABE Hirofumi <eban@...>

[#14530] restore terminal mode even if readline interrupted. — Koji Arai <JCA02266@...>

[#14547] setuid/setgid — nobu.nakada@...

[#14552] read in IO#eof? — nobu.nakada@...

[#14560] — nobu.nakada@...

[#14565] (mswin32) dln_strerror() returns empty message — Tietew <tietew@...>

[#14572] noisy warnings of resolv.rb — Koji Arai <JCA02266@...>

[#14573] [PATCH] ruby-mode.el — Kenichi Komiya <kom@...1.accsnet.ne.jp>

[#14575] infinite loop on Dir.glob("*/**/*") — nobu.nakada@...

[#14576] glob_helper: merge from 1.7 — nobu.nakada@...

[#14577] option nodynamic — Daisuke Aoki <dai@...>

[#14584] Array#merge, Array#squeeze — "Akinori MUSHA" <knu@...>

[#14590] rb_load — OJ <oj@...7.com>

[#14595] SEGV at `$0 = "long long string"' — nobu.nakada@...

[#14601] $stdout への代入 ( 再考) — Koji Arai <JCA02266@...>

[#14603] patch for GNU/Hurd — akira yamada / やまだあきら <akira@...>

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

Thread

In This Thread

[#14300] 名前空間を調べる効果的な方法はありますか？ — 西啓一朗 <receiver@...>

[#14445] string.c rb_str_cmp() — TOYOFUKU　Chikanobu <toyofuku@...>