From 451574f1420d8533f44a06d9aca23b5647292228 Mon Sep 17 00:00:00 2001
From: Christopher Aue <mail@christopheraue.net>
Date: Fri, 28 Jul 2017 17:02:36 +0200
Subject: Refactored Array#bsearch

---
 mrbgems/mruby-array-ext/mrblib/array.rb | 34 +++++++++++++++++++--------------
 1 file changed, 20 insertions(+), 14 deletions(-)

(limited to 'mrbgems/mruby-array-ext/mrblib/array.rb')

diff --git a/mrbgems/mruby-array-ext/mrblib/array.rb b/mrbgems/mruby-array-ext/mrblib/array.rb
index 1e6d4d581..b5c2e7c47 100644
--- a/mrbgems/mruby-array-ext/mrblib/array.rb
+++ b/mrbgems/mruby-array-ext/mrblib/array.rb
@@ -596,30 +596,36 @@ class Array
     return to_enum :bsearch unless block_given?
 
     low = 0
-    high = self.size
+    high = size
     satisfied = false
+
     while low < high
-      mid = low + ((high - low) / 2).truncate
+      mid = ((low+high)/2).truncate
       val = self[mid]
-      v = block.call(val)
-      if v.is_a?(Integer)
-        return val if v == 0
-        smaller = v < 0
-      elsif v == true
+      res = block.call val
+
+      case res
+      when 0 # find-any mode: Found!
+        return val
+      when Numeric # find-any mode: Continue...
+        in_lower_half = res < 0
+      when true # find-min mode
+        in_lower_half = true
         satisfied = true
-        smaller = true
-      elsif v == false || v.nil?
-        smaller = false
+      when false, nil # find-min mode
+        in_lower_half = false
+      else
+        raise TypeError, 'invalid block result (must be numeric, true, false or nil)'
       end
-      if smaller
+
+      if in_lower_half
         high = mid
       else
         low = mid + 1
       end
     end
-    return nil if low == self.size
-    return nil unless satisfied
-    self[low]
+
+    satisfied ? self[low] : nil
   end
 
   ##
-- 
cgit v1.2.3


From a3bfd735a041078cd9497c739fb3e21efc0c36f0 Mon Sep 17 00:00:00 2001
From: Christopher Aue <mail@christopheraue.net>
Date: Fri, 28 Jul 2017 17:08:35 +0200
Subject: Added Array#bsearch_index

---
 mrbgems/mruby-array-ext/mrblib/array.rb | 29 +++++++++++++++++++++++++----
 mrbgems/mruby-array-ext/test/array.rb   |  4 ++++
 2 files changed, 29 insertions(+), 4 deletions(-)

(limited to 'mrbgems/mruby-array-ext/mrblib/array.rb')

diff --git a/mrbgems/mruby-array-ext/mrblib/array.rb b/mrbgems/mruby-array-ext/mrblib/array.rb
index b5c2e7c47..716eabe06 100644
--- a/mrbgems/mruby-array-ext/mrblib/array.rb
+++ b/mrbgems/mruby-array-ext/mrblib/array.rb
@@ -595,18 +595,39 @@ class Array
   def bsearch(&block)
     return to_enum :bsearch unless block_given?
 
+    if idx = bsearch_index(&block)
+      self[idx]
+    else
+      nil
+    end
+  end
+
+  ##
+  #  call-seq:
+  #     ary.bsearch_index {|x| block }  -> int or nil
+  #
+  #  By using binary search, finds an index of a value from this array which
+  #  meets the given condition in O(log n) where n is the size of the array.
+  #
+  #  It supports two modes, depending on the nature of the block and they are
+  #  exactly the same as in the case of #bsearch method with the only difference
+  #  being that this method returns the index of the element instead of the
+  #  element itself. For more details consult the documentation for #bsearch.
+
+  def bsearch_index(&block)
+    return to_enum :bsearch_index unless block_given?
+
     low = 0
     high = size
     satisfied = false
 
     while low < high
       mid = ((low+high)/2).truncate
-      val = self[mid]
-      res = block.call val
+      res = block.call self[mid]
 
       case res
       when 0 # find-any mode: Found!
-        return val
+        return mid
       when Numeric # find-any mode: Continue...
         in_lower_half = res < 0
       when true # find-min mode
@@ -625,7 +646,7 @@ class Array
       end
     end
 
-    satisfied ? self[low] : nil
+    satisfied ? low : nil
   end
 
   ##
diff --git a/mrbgems/mruby-array-ext/test/array.rb b/mrbgems/mruby-array-ext/test/array.rb
index 401d30a5e..c0db1b1cc 100644
--- a/mrbgems/mruby-array-ext/test/array.rb
+++ b/mrbgems/mruby-array-ext/test/array.rb
@@ -267,6 +267,10 @@ assert("Array#bsearch") do
   end
 end
 
+assert("Array#bsearch_index") do
+  # tested through Array#bsearch
+end
+
 assert("Array#delete_if") do
   a = [1, 2, 3, 4, 5]
   assert_equal [1, 2, 3, 4, 5], a.delete_if { false }
-- 
cgit v1.2.3