ꦫꦣꦺꦤ꧀ꦄꦤ꧀ꦠꦱꦺꦤ

PATH: opt / alt / ruby34 / share / ri / system

U:RDoc::TopLevel[	i�I"bsearch.rdoc:ETcRDoc::Parser::Simpleo:RDoc::Markup::Document:@parts[8S:RDoc::Markup::Heading:
leveli:	textI"Binary Searching;To:RDoc::Markup::BlankLine�o:RDoc::Markup::Paragraph;[I"AA few Ruby methods support binary searching in a collection:;T@
o:RDoc::Markup::List:
@type:	NOTE:@items[o:RDoc::Markup::ListItem:@label[I"Array#bsearch;T;[o;
;[I"5Returns an element selected via a binary search ;TI"$as determined by a given block.;To;;[I"Array#bsearch_index;T;[o;
;[I"BReturns the index of an element selected via a binary search ;TI"$as determined by a given block.;To;;[I"Range#bsearch;T;[o;
;[I"5Returns an element selected via a binary search ;TI"$as determined by a given block.;T@
o;
;[I"FEach of these methods returns an enumerator if no block is given.;T@
o;
;[
I"\Given a block, each of these methods returns an element (or element index) from +self+ ;TI"'as determined by a binary search. ;TI"7The search finds an element of +self+ which meets ;TI"^the given condition in <tt>O(log n)</tt> operations, where +n+ is the count of elements. ;TI"6+self+ should be sorted, but this is not checked.;T@
o;
;[I" There are two search modes:;T@
o;;;;[o;;[I"Find-minimum mode;T;[o;
;[I":method +bsearch+ returns the first element for which ;TI"the block returns +true+; ;TI"-the block must return +true+ or +false+.;To;;[I"Find-any mode;T;[o;
;[I"6method +bsearch+ some element, if any, for which ;TI"the block returns zero. ;TI"+the block must return a numeric value.;T@
o;
;[I"QThe block should not mix the modes by sometimes returning +true+ or +false+ ;TI"Hand other times returning a numeric value, but this is not checked.;T@
o;
;[I"<b>Find-Minimum Mode</b>;T@
o;
;[I"DIn find-minimum mode, the block must return +true+ or +false+. ;TI":The further requirement (though not checked) is that ;TI"0there are no indexes +i+ and +j+ such that:;T@
o;;:BULLET;[o;;0;[o;
;[I"&<tt>0 <= i < j <= self.size</tt>.;To;;0;[o;
;[I"TThe block returns +true+ for <tt>self[i]</tt> and +false+ for <tt>self[j]</tt>.;T@
o;
;[I"KLess formally: the block is such that all +false+-evaluating elements ;TI",precede all +true+-evaluating elements.;T@
o;
;[I"FIn find-minimum mode, method +bsearch+ returns the first element ;TI"(for which the block returns +true+.;T@
o;
;[I"Examples:;T@
o:RDoc::Markup::Verbatim;[I"a = [0, 4, 7, 10, 12]
;TI"$a.bsearch {|x| x >= 4 } # => 4
;TI"$a.bsearch {|x| x >= 6 } # => 7
;TI"%a.bsearch {|x| x >= -1 } # => 0
;TI"(a.bsearch {|x| x >= 100 } # => nil
;TI"
;TI"r = (0...a.size)
;TI"&r.bsearch {|i| a[i] >= 4 } #=> 1
;TI"&r.bsearch {|i| a[i] >= 6 } #=> 2
;TI"&r.bsearch {|i| a[i] >= 8 } #=> 3
;TI"*r.bsearch {|i| a[i] >= 100 } #=> nil
;TI"!r = (0.0...Float::INFINITY)
;TI"/r.bsearch {|x| Math.log(x) >= 0 } #=> 1.0
;T:@format0o;
;[I"2These blocks make sense in find-minimum mode:;T@
o;;[
I"a = [0, 4, 7, 10, 12]
;TI">a.map {|x| x >= 4 } # => [false, true, true, true, true]
;TI"?a.map {|x| x >= 6 } # => [false, false, true, true, true]
;TI">a.map {|x| x >= -1 } # => [true, true, true, true, true]
;TI"Da.map {|x| x >= 100 } # => [false, false, false, false, false]
;T;0o;
;[I"This would not make sense:;T@
o;;[I"Aa.map {|x| x == 7 } # => [false, false, true, false, false]
;T;0o;
;[I"<b>Find-Any Mode</b>;T@
o;
;[I">In find-any mode, the block must return a numeric value. ;TI":The further requirement (though not checked) is that ;TI"0there are no indexes +i+ and +j+ such that:;T@
o;;;;[	o;;0;[o;
;[I"&<tt>0 <= i < j <= self.size</tt>.;To;;0;[o;
;[I"=The block returns a negative value for <tt>self[i]</tt> ;TI"/and a positive value for <tt>self[j]</tt>.;To;;0;[o;
;[I"WThe block returns a negative value for <tt>self[i]</tt> and zero <tt>self[j]</tt>.;To;;0;[o;
;[I"[The block returns zero for <tt>self[i]</tt> and a positive value for <tt>self[j]</tt>.;T@
o;
;[I"+Less formally: the block is such that:;T@
o;;;;[o;;0;[o;
;[I"KAll positive-evaluating elements precede all zero-evaluating elements.;To;;0;[o;
;[I"OAll positive-evaluating elements precede all negative-evaluating elements.;To;;0;[o;
;[I"KAll zero-evaluating elements precede all negative-evaluating elements.;T@
o;
;[I"=In find-any mode, method +bsearch+ returns some element ;TI"Lfor which the block returns zero, or +nil+ if no such element is found.;T@
o;
;[I"Examples:;T@
o;;[I"a = [0, 4, 7, 10, 12]
;TI"1a.bsearch {|element| 7 <=> element } # => 7
;TI"4a.bsearch {|element| -1 <=> element } # => nil
;TI"3a.bsearch {|element| 5 <=> element } # => nil
;TI"4a.bsearch {|element| 15 <=> element } # => nil
;TI"
;TI"!a = [0, 100, 100, 100, 200]
;TI"r = (0..4)
;TI"/r.bsearch {|i| 100 - a[i] } #=> 1, 2 or 3
;TI")r.bsearch {|i| 300 - a[i] } #=> nil
;TI")r.bsearch {|i|  50 - a[i] } #=> nil
;T;0o;
;[I".These blocks make sense in find-any mode:;T@
o;;[
I"a = [0, 4, 7, 10, 12]
;TI"=a.map {|element| 7 <=> element } # => [1, 1, 0, -1, -1]
;TI"Aa.map {|element| -1 <=> element } # => [-1, -1, -1, -1, -1]
;TI">a.map {|element| 5 <=> element } # => [1, 1, -1, -1, -1]
;TI"<a.map {|element| 15 <=> element } # => [1, 1, 1, 1, 1]
;T;0o;
;[I"This would not make sense:;T@
o;;[I"<a.map {|element| element <=> 7 } # => [-1, -1, 0, 1, 1];T;0:
@file@:0@omit_headings_from_table_of_contents_below0

[+] ..
[+] UnicodeNormalize
[+] OptionParser
[+] Integer
[+] Ractor
[+] Bundler
[-] page-implicit_conversion_rdoc.ri [edit]
[+] Digest
[+] Addrinfo
[-] cache.ri [edit]
[+] FloatDomainError
[+] TCPServer
[+] KeyError
[+] SystemCallError
[+] RactorLocalSingleton
[+] Prism
[+] Exception
[+] SystemStackError
[+] Hash
[+] Math
[+] Rational
[+] NEWS
[+] Timeout
[-] page-fiber_md.ri [edit]
[-] page-extension_rdoc.ri [edit]
[+] Shellwords
[-] page-maintainers_md.ri [edit]
[-] page-marshal_rdoc.ri [edit]
[+] English
[+] Process
[+] GC
[-] page-extension_ja_rdoc.ri [edit]
[+] FiberError
[-] page-dig_methods_rdoc.ri [edit]
[+] Singleton
[+] ARGF
[+] StringScanner
[+] Fcntl
[-] page-command_injection_rdoc.ri [edit]
[+] File
[+] ArgumentError
[-] page-LEGAL.ri [edit]
[+] Interrupt
[+] IPAddr
[+] Benchmark
[+] Enumerator
[+] UDPSocket
[+] Monitor
[-] page-NEWS_md.ri [edit]
[+] ENV
[+] RubyVM
[-] page-index_md.ri [edit]
[+] WeakRef
[+] Reline
[+] Class
[+] EncodingError
[-] page-COPYING_ja.ri [edit]
[+] TCPSocket
[+] SOCKSSocket
[-] page-globals_rdoc.ri [edit]
[+] Net
[+] Dir
[+] Random
[+] Signal
[-] page-format_specifications_rdoc.ri [edit]
[-] page-distribution_md.ri [edit]
[+] MonitorMixin
[+] Complex
[+] SystemExit
[-] page-strftime_formatting_rdoc.ri [edit]
[-] page-COPYING.ri [edit]
[+] Proc
[+] UNIXSocket
[+] StringIO
[+] Refinement
[+] Readline
[+] Struct
[+] RbConfig
[+] PrettyPrint
[+] RangeError
[-] page-contributing_md.ri [edit]
[-] page-ractor_md.ri [edit]
[+] PTY
[+] NameError
[+] WIN32OLE
[+] NoMethodError
[+] Range
[+] Date
[-] page-bsearch_rdoc.ri [edit]
[+] OLEProperty
[+] NotImplementedError
[+] FileTest
[+] Regexp
[+] Kernel
[+] BasicObject
[-] page-packed_data_rdoc.ri [edit]
[+] Fiddle
[+] UnboundMethod
[+] Open3
[+] optparse
[+] Marshal
[+] MatchData
[+] regexp
[+] Object
[+] Coverage
[-] page-encodings_rdoc.ri [edit]
[+] ThreadError
[-] page-memory_view_md.ri [edit]
[-] page-dtrace_probes_rdoc.ri [edit]
[+] NoMemoryError
[+] UNIXServer
[+] Resolv
[-] page-windows_md.ri [edit]
[+] date
[+] TSort
[+] EOFError
[+] Method
[-] page-security_rdoc.ri [edit]
[+] URI
[+] OpenStruct
[+] FrozenError
[-] page-README_ja_md.ri [edit]
[+] IndexError
[+] ERB
[+] Comparable
[+] PStore
[+] Ripper
[+] Gem
[+] SecurityError
[+] Pathname
[+] Warning
[+] Thread
[+] LoadError
[+] RegexpError
[+] Float
[+] Numeric
[+] SyntaxSuggest
[+] RDoc
[+] Rake
[+] StandardError
[+] FalseClass
[-] page-README_md.ri [edit]
[-] page-character_selectors_rdoc.ri [edit]
[+] Encoding
[+] Time
[+] YAML
[+] MakeMakefile
[+] UncaughtThrowError
[+] Delegator
[-] page-signals_rdoc.ri [edit]
[+] Enumerable
[+] StopIteration
[+] ObjectSpace
[+] ClosedQueueError
[+] OpenSSL
[-] page-standard_library_md.ri [edit]
[+] ErrorHighlight
[+] IO
[+] BasicSocket
[+] BigDecimal
[+] Win32
[+] Logger
[+] PP
[+] Continuation
[+] SingleForwardable
[+] CGI
[+] JSON
[+] fatal
[+] yjit
[+] Module
[+] Data
[+] TypeError
[+] ThreadGroup
[+] Zlib
[+] OpenURI
[+] SimpleDelegator
[+] Find
[+] syntax
[+] ruby
[+] SignalException
[+] FileUtils
[+] ScriptError
[+] rjit
[+] contributing
[+] ZeroDivisionError
[+] TrueClass
[+] NoMatchingPatternKeyError
[+] DidYouMean
[+] RuntimeError
[+] DateTime
[+] CoreExtensions
[-] page-syntax_rdoc.ri [edit]
[-] page-exceptions_md.ri [edit]
[-] page-bug_triaging_rdoc.ri [edit]
[+] Etc
[+] IOError
[+] Errno
[+] Fiber
[+] Symbol
[+] LocalJumpError
[+] TracePoint
[+] NilClass
[+] Forwardable
[-] page-case_mapping_rdoc.ri [edit]
[+] Array
[+] NoMatchingPatternError
[+] IPSocket
[+] SyntaxError
[+] Binding
[+] SocketError
[+] Set
[+] String
[+] Socket
[+] SecureRandom
[+] Psych
[+] Tempfile