我如何计算 iterations/steps 的数量以找到方法的答案 - RUBY

Question

如何获得此方法找到答案所需的 iterations/steps 次数？

def binary_search(array, n)
 min = 0
 max = (array.length) - 1

 while min <= max
     middle = (min + max) / 2

    if array[middle] == n
          return middle
     elsif array[middle] > n
         max = middle - 1
     elsif array[middle] < n
       min = middle + 1
     end 
     end 
    "#{n} not found in this array"
 end

Answer 1

只需计算迭代次数即可。

在循环外将变量设置为 0
在循环里面给它加1
当您 return 索引时，return 计数 (return [middle, count])。

Answer 2

可以代替计数器使用的一个选项是 .with_index 关键字。要使用它，您需要使用 loop 而不是 while，但它应该是一样的。这是一个带输出的基本示例。

arr = [1,2,3,4,5,6,7,8]
loop.with_index do |_, index| # The underscore is to ignore the first variable as it's not used
  if (arr[index] % 2).zero?
    puts "even: #{arr[index]}"
  else
    puts "odd: #{arr[index]}"
  end

  break if index.eql?(arr.length - 1)
end

=>
odd: 1
even: 2
odd: 3
even: 4
odd: 5
even: 6
odd: 7
even: 8

Answer 3

我假设计算 binary_search 所需的交互次数的代码将用于测试或优化。如果是这样，方法 binary_search 应该修改为生成生产代码，只需要删除（或注释掉）代码行，而不是修改语句。这是一种可行的方法。

def binary_search(array, n)
  # remove from production code lines marked ->              #******
  _bin_srch_iters = 0                                        #******
  begin                                                      #******
    min = 0
    max = (array.length) - 1
    loop do
      _bin_srch_iters += 1                                   #******
      middle = (min + max) / 2
      break middle if array[middle] == n
      break nil if min == max  
      if array[middle] > n
        max = middle - 1
      else # array[middle] < n
        min = middle + 1
      end 
    end
  ensure                                                     #****** 
    puts "binary_search reqd #{_bin_srch_iters} interations" #******  
  end                                                        #******
end

x = binary_search([1,3,6,7,9,11], 3)
#   binary_search reqd 3 interations
#=> 1

binary_search([1,3,6,7,9,11], 5) 
#   binary_search reqd 3 interations
#=> nil

我如何计算 iterations/steps 的数量以找到方法的答案 - RUBY

How can I count number of iterations/steps to find answers of a method - RUBY

ruby

binary-search