Question

面试时候如何用 Ruby 写一个最短二分查找代码 · Ruby China

Answer 1

def binary_search(arr, key)
  low = 0
  high = arr.size - 1
  
  while(low <= high) do
    mid = low + (high - low) / 2
    
    if arr[mid] == key
      return mid
    elsif arr[mid] < key
      low = mid + 1
    else
      high = mid - 1
    end
  end
  
  return 'not found'
end

ruby 2.0之后Array中内置了bsearch以及bsearch_index方法，参考：http://ruby-doc.org/core-2.4.0/Array.html#method-i-bsearch