Create a gist now

Instantly share code, notes, and snippets.

@mvj3 /.gitignore
Last active Sep 25, 2015

What would you like to do?
二分查找
binary_search.rbc

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

声明: 以下描述并非抱怨,而只是针对面试中的算法题,希望给别人提供点借鉴,更多地清醒头脑,理清思路,跳出当时的思维局限,和面试官互动解决掉面试题。

本人技术背景: 全栈式Ruby on Rails开发四年多,并在大数据分析方面有些经验,详见个人主页 http://mvj3.github.io


今天面试的时候被要求手写二分查找代码。

这让我不由得想起几年前去yottaa面试要求手写二分查找代码时失败的窘迫来。于是我和面试官提了说,有人说过 专业程序员里的90%都无法正确实现二分查找 ,而且我之前用 二分查找实现过日志二分查找 ,大概原理就是不断依据范围进行折半查找。面试官还是要求现场写一个,于是我只好硬着头皮开始写了,不断回想和思考里面的边界和技巧,脑子里一团乱,在纸上写实在没感觉(因为要运行程序测试嘛,本人的大脑还不是CPU。。。),就打开自己带的笔记本开始写了。

测试代码是:

puts binary_search((1..15).to_a, 8) == 7
puts binary_search((1..15).to_a, 1) == 0
puts binary_search((1..15).to_a, 14) == 13
puts binary_search([2,3,8,15], 8) == 2

这个没有疑问。然后先写了代码的轮廓,因为之前项目有好多模块都是通过递归实现的,就构造了一下 binary_search array, value, from, to 这样的API,最终代码是:

def binary_search array, value, from = nil, to = nil
  return nil if array.blank?

  from ||= 0
  to   ||= array.size
  mid_idx = ((from + to) / 2.0).round
  mid_val = array[mid_idx]

  if value == mid_val
    return mid_idx
  elsif value > mid_val
    binary_search array, value, (mid_idx+1), to
  else
    binary_search array, value, from, (mid_idx-1)
  end
end

测试通过。面试官反应用迭代方式实现,他说有性能问题。这里稍微和他有些讨论,迭代就迭代吧,我和他说那就用这第二种方式实现。

这次写的时间比较久,估计在二三十分钟,遇到死循环的问题。途中和面试官抱怨了一句,他回说就是考边界。最终调试无果(当时我严重怀疑是边界出了问题,但是我想不起那个准确的解法),就说和面试官一起看看吧。

def binary_search array, value
  @idx = nil

  loop do
    @from ||= 0
    @to   ||= (array.size - 1)

    return nil if array[@from..@to].blank?

    puts "+ #{@from + @to}"
    @idx = ((@from + @to) / 2.0).round
    puts "[#{@from}, #{@to}] #{@idx}"
    #binding.pry

    mid_val = array[@idx]

    if value == mid_val
      break
    elsif value > mid_val
      @from = @idx.round
      break if value == array[((@from + @to) / 2.0).round]
    else
      @to = @idx.round
      break if value == array[((@from + @to) / 2.0).ceil]
    end
  end

  return @idx
end

上面在跑前二个用例是准确的,但是第三个有点异常了,现在回来一看才发现是实例变量在方法多次调用后混淆的问题。而其中出现round和ceil之类方法的原因是他和我提到了之前远程面试时做的一个题目里我没有用 String#chars 这样更Ruby的写法,而是用了 str.split(//) ,所以我潜意识里可能顺着他的这个原则走了,当然这里的路走错了。

下面的是我现在改好的:

def binary_search array, value
  puts "查找数组 #{array}, 值 #{value}" if ENV["DEBUG"]
  from, to, idx = 0, array.size.pred, nil
  loop do
    return nil if array[from..to].blank?

    idx = (from + to) / 2
    mid_val = array[idx]
    puts "起始 #{from}, 终止 #{to}, 当前索引 #{idx}"  if ENV["DEBUG"]

    if value == mid_val
      break
    elsif value > mid_val
      from = idx + 1
    else
      to = idx - 1
    end
  end

  return idx
end

在和他讨论这个迭代的死循环代码时,他指明写的太冗余了,好的写法应该可以更短。这个就突然提示了我想起以前其实在yottaa面试结束后回家就调查了相关资料,然后写过 这两个版本 的,里面还包括插入功能,更深的影响就是加入eoe后写了上面提到的logpos日志二分查找模块。

然后我打开以前保存的代码,给他看,他反馈说还是可以更短。我说能不能找给我看。他说你回去可以自己找。

现在回来搜了一个迭代版本的, http://gistflow.com/posts/199-binary-search-with-ruby-and-tdd

class Array
  def iterative_bindex element, lower = 0, upper = length - 1
    while upper >= lower
      mid = (upper + lower) / 2
      if self[mid] < element
        lower = mid + 1
      elsif self[mid] > element
        upper = mid - 1
      else
        return mid
      end
    end

    return nil
  end
end

按语义来说,包括关键字和方法, %W[class Array def iterative_bindex element lower = 0 upper = length - 1 while upper >= lower mid = () upper + lower / 2 if self[] mid < element lower = mid + 1 elsif self [] mid > element upper = mid - 1 else return mid end end return nil end end] ,为55个词。

而我回来后实现的版本, %W[def binary_search array value from to idx = 0 array size pred nil loop do return nil if array [] from .. to blank? idx = () from + to / 2 mid_val = array [] idx if value == mid_val break elsif value > mid_val from = idx + 1 else to = idx - 1 end end return idx end] 为62个词。

我个人觉得两者无甚区别。不知道哪位大牛可以给出更短的Ruby版本,标准算40个词吧。

最后面试官总结我应用或Rails方面的经验比较多,但是算法不太行,他准备和CEO再讨论看看。于是我咨询他公司技术部有哪些算法工作,他提了一个数据排重,然后我说如果准确度不太要求的话,可以用bloomfilter进行过滤。但是他坚持这一轮面试结束了,于是只能出门和他道别了。

额,只能等后续再沟通了,总之有点冤。。。


本人之前写过 前端工程师的面试也可以如此生动 ,过段时间也总结一篇如何面试Ruby工程师的文章吧。

# 二分查找(又称折半查找)是在一个有序表里查找元素的复杂度为O(log(n))的算法。先从中间位置开始比较,相等则返回,如小于中间值,则将接下来的查找范围设定为前一子表,大于则为后一子表,以下如此类推。
# 维基百科参考:http://en.wikipedia.org/wiki/Binary_search_algorithm
class Array
# 迭代版本
def binary_search_in_iterative num, insert = true
min, max = 0, self.size - 1
while min <= max
mid = (min + max) / 2
if num < self[mid]
max = mid - 1
elsif num == self[mid]
return mid
else
min = mid + 1
end
end
insert_item num, min, mid if insert
return nil if min > max
end
# 递归版本
def binary_search_in_recursive num, insert = true, min = nil, max = nil
min ||= 0
max ||= self.size - 1
mid = (min + max) / 2
if min > max
insert_item num, min, mid if insert
return nil
end
if num > self[mid]
binary_search_in_recursive num, insert, mid + 1 , max
elsif num < self[mid]
binary_search_in_recursive num, insert, min, mid - 1
else
return mid
end
end
def insert_item num, min, mid
min = mid if self[min].nil?
self[min..min] = (self[min] < num) ? [self[min], num] : [num, self[min]]
end
end
require 'benchmark'
array = (0..6**7).to_a
puts "数组是从0到#{array[-1]}的之间的所有整数"
[-1, -6**3, 0, 4**5, 6**6].each do |num|
puts "匹配#{num}"
Benchmark.bm do |x|
x.report("index ") { array.index num }
x.report("iterative") { array.binary_search_in_iterative num, false }
x.report("recursive") { array.binary_search_in_recursive num, false }
end
puts
end
__END__
以下是运行本程序的结果
数组是从0279936的之间的所有整数
匹配-1
user system total real
index 0.010000 0.000000 0.010000 ( 0.014947)
iterative 0.000000 0.000000 0.000000 ( 0.000048)
recursive 0.000000 0.000000 0.000000 ( 0.000065)
匹配-216
user system total real
index 0.010000 0.000000 0.010000 ( 0.014744)
iterative 0.000000 0.000000 0.000000 ( 0.000028)
recursive 0.000000 0.000000 0.000000 ( 0.000040)
匹配0
user system total real
index 0.000000 0.000000 0.000000 ( 0.000005)
iterative 0.000000 0.000000 0.000000 ( 0.000019)
recursive 0.000000 0.000000 0.000000 ( 0.000032)
匹配1024
user system total real
index 0.000000 0.000000 0.000000 ( 0.000059)
iterative 0.000000 0.000000 0.000000 ( 0.000031)
recursive 0.000000 0.000000 0.000000 ( 0.000048)
匹配46656
user system total real
index 0.000000 0.000000 0.000000 ( 0.003513)
iterative 0.000000 0.000000 0.000000 ( 0.000022)
recursive 0.000000 0.000000 0.000000 ( 0.000045)
从上面可以看到,迭代都比递归快一倍左右,不难看出Ruby里默认的数组查找是直接在线性时间里遍历查找的,查看Array#index对应的C源码一看便知。
static VALUE
rb_ary_index(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
VALUE val;
long i;
if (argc == 0) {
RETURN_ENUMERATOR(ary, 0, 0);
for (i=0; i<RARRAY(ary)->len; i++) {
if (RTEST(rb_yield(RARRAY(ary)->ptr[i]))) {
return LONG2NUM(i);
}
}
return Qnil;
}
rb_scan_args(argc, argv, "01", &val);
for (i=0; i<RARRAY(ary)->len; i++) {
if (rb_equal(RARRAY(ary)->ptr[i], val))
return LONG2NUM(i);
}
return Qnil;
}

Ruby默认实现为什么是遍历查找的?慢啊。

Owner

mvj3 commented Sep 23, 2014

@chenyukang 因为Ruby不能保证你的Array是排序过的。在没排序的Array里进行二分查找,会因为跳跃而导致找不到那个真正要找的元素。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment