doc/bsearch.rdoc

   1 = Binary Searching
   2
   3 A few Ruby methods support binary searching in a collection:
   4
   5 Array#bsearch:: Returns an element selected via a binary search
   6                 as determined by a given block.
   7 Array#bsearch_index:: Returns the index of an element selected via a binary search
   8                       as determined by a given block.
   9 Range#bsearch:: Returns an element selected via a binary search
  10                 as determined by a given block.
  11
  12 Each of these methods returns an enumerator if no block is given.
  13
  14 Given a block, each of these methods returns an element (or element index) from +self+
  15 as determined by a binary search.
  16 The search finds an element of +self+ which meets
  17 the given condition in <tt>O(log n)</tt> operations, where +n+ is the count of elements.
  18 +self+ should be sorted, but this is not checked.
  19
  20 There are two search modes:
  21
  22 Find-minimum mode:: method +bsearch+ returns the first element for which
  23                     the block returns +true+;
  24                     the block must return +true+ or +false+.
  25 Find-any mode:: method +bsearch+ some element, if any, for which
  26                 the block returns zero.
  27                 the block must return a numeric value.
  28
  29 The block should not mix the modes by sometimes returning +true+ or +false+
  30 and other times returning a numeric value, but this is not checked.
  31
  32 <b>Find-Minimum Mode</b>
  33
  34 In find-minimum mode, the block must return +true+ or +false+.
  35 The further requirement (though not checked) is that
  36 there are no indexes +i+ and +j+ such that:
  37
  38 - <tt>0 <= i < j <= self.size</tt>.
  39 - The block returns +true+ for <tt>self[i]</tt> and +false+ for <tt>self[j]</tt>.
  40
  41 Less formally: the block is such that all +false+-evaluating elements
  42 precede all +true+-evaluating elements.
  43
  44 In find-minimum mode, method +bsearch+ returns the first element
  45 for which the block returns +true+.
  46
  47 Examples:
  48
  49   a = [0, 4, 7, 10, 12]
  50   a.bsearch {|x| x >= 4 } # => 4
  51   a.bsearch {|x| x >= 6 } # => 7
  52   a.bsearch {|x| x >= -1 } # => 0
  53   a.bsearch {|x| x >= 100 } # => nil
  54
  55   r = (0...a.size)
  56   r.bsearch {|i| a[i] >= 4 } #=> 1
  57   r.bsearch {|i| a[i] >= 6 } #=> 2
  58   r.bsearch {|i| a[i] >= 8 } #=> 3
  59   r.bsearch {|i| a[i] >= 100 } #=> nil
  60   r = (0.0...Float::INFINITY)
  61   r.bsearch {|x| Math.log(x) >= 0 } #=> 1.0
  62
  63 These blocks make sense in find-minimum mode:
  64
  65   a = [0, 4, 7, 10, 12]
  66   a.map {|x| x >= 4 } # => [false, true, true, true, true]
  67   a.map {|x| x >= 6 } # => [false, false, true, true, true]
  68   a.map {|x| x >= -1 } # => [true, true, true, true, true]
  69   a.map {|x| x >= 100 } # => [false, false, false, false, false]
  70
  71 This would not make sense:
  72
  73   a.map {|x| x == 7 } # => [false, false, true, false, false]
  74
  75 <b>Find-Any Mode</b>
  76
  77 In find-any mode, the block must return a numeric value.
  78 The further requirement (though not checked) is that
  79 there are no indexes +i+ and +j+ such that:
  80
  81 - <tt>0 <= i < j <= self.size</tt>.
  82 - The block returns a negative value for <tt>self[i]</tt>
  83   and a positive value for <tt>self[j]</tt>.
  84 - The block returns a negative value for <tt>self[i]</tt> and zero <tt>self[j]</tt>.
  85 - The block returns zero for <tt>self[i]</tt> and a positive value for <tt>self[j]</tt>.
  86
  87 Less formally: the block is such that:
  88
  89 - All positive-evaluating elements precede all zero-evaluating elements.
  90 - All positive-evaluating elements precede all negative-evaluating elements.
  91 - All zero-evaluating elements precede all negative-evaluating elements.
  92
  93 In find-any mode, method +bsearch+ returns some element
  94 for which the block returns zero, or +nil+ if no such element is found.
  95
  96 Examples:
  97
  98   a = [0, 4, 7, 10, 12]
  99   a.bsearch {|element| 7 <=> element } # => 7
 100   a.bsearch {|element| -1 <=> element } # => nil
 101   a.bsearch {|element| 5 <=> element } # => nil
 102   a.bsearch {|element| 15 <=> element } # => nil
 103
 104   a = [0, 100, 100, 100, 200]
 105   r = (0..4)
 106   r.bsearch {|i| 100 - a[i] } #=> 1, 2 or 3
 107   r.bsearch {|i| 300 - a[i] } #=> nil
 108   r.bsearch {|i|  50 - a[i] } #=> nil
 109
 110 These blocks make sense in find-any mode:
 111
 112   a = [0, 4, 7, 10, 12]
 113   a.map {|element| 7 <=> element } # => [1, 1, 0, -1, -1]
 114   a.map {|element| -1 <=> element } # => [-1, -1, -1, -1, -1]
 115   a.map {|element| 5 <=> element } # => [1, 1, -1, -1, -1]
 116   a.map {|element| 15 <=> element } # => [1, 1, 1, 1, 1]
 117
 118 This would not make sense:
 119
 120   a.map {|element| element <=> 7 } # => [-1, -1, 0, 1, 1]