Ruby、演算法学习心得(一) 二元搜寻法 Binary Search。

铁人赛结束後一阵空虚??
文章内容都会以Ruby来撰写程序码，然後继续来传教K-POP啦!

有请韩国国民妹妹IU来献唱第一首!

转载於:Jaxirius个人YouTube

何为演算法?

简单一点说，把一些我们想解决的算术问题，设计出一套公式，写成程序让电脑运作，这些公式就是演算法。

学了演算法就会写程序?

那当然一定是两回事，不过学演算法可以帮助自己了解一些逻辑概念，看多了或许就会懂别人为何设计出那样的程序，以及运用的逻辑为何，一定程度上能帮助自己对程序语言的了解。

演算法与特殊语法的差异。

演算法是为了加速问题解决的时间，或减少电脑解决问题所需花的记忆体。

程序语言都有自己的函式库或特殊语法，能让学习者用最少的时间，写出最简短精要的code，例如我是学Ruby的，是程序语言中黑魔法(特殊语法)数一数二多的，那些特殊语法用起来非常便利，但不一定是针对自己想解决的问题而设计。

两者最大的差异就在特殊语法给予工程师便捷，而演算法目的在减少所耗资源。

二元搜寻法 Binary Search

二元搜寻有个使用限制，使用时资料是需经过排序的。

举例一个最常被用来说明的例子，猜数字。

假设1~100中选一个数字要给对方猜，对方从1说到99要执行99次，99再不对100当然也就是答案了，所以这样设计程序，等於需要让电脑执行最多99次得到运算，虽然有机率一次就猜到，但那也是1/100的机率。

def guess_number(ans)
  (1..100).each do |num|
    return true if num == ans
    puts num
  end
end

puts guess_number(50)  #会跑出1~49 然後传出true

而二元搜寻法则是像这样操作。(一样1~100，正确答案是87。)

告诉电脑:找50! (我们一开始就去掉了一半)

电脑回答:太低。

告诉电脑:找75! (51~100再去掉了一半)

电脑回答:太低。

告诉电脑:找88! (76~100再去掉一半)

电脑回答:太高。

告诉电脑:找82! (76~88再去掉一半)

电脑回答:太低。

告诉电脑:找85! (83~88再去掉一半)

电脑回答:太低。

告诉电脑:找87! (86跟88的中间刚好是答案)

电脑回答:正确。总共找了6次，而如果是跑回圈由1开始跑到100那最少要跑86次，这还只是1~100假设有个10万笔的资料要找，那就是再快的电脑也会跑得很累。

将上面的逻辑换成程序码。

def guess_number(ans)
  low = 1
  high = 100
  guess_times = 0
  while low <= high
    guess = (low + high) / 2
    if guess == ans
      return guess_times
    elsif guess > ans
      high = guess - 1
      guess_times += 1
      puts guess
    else
      low = guess + 1
      guess_times += 1
      puts guess
    end
  end
end

puts guess_number(87)  #得到猜过的数字及跑过几次。

当然不是永用都6次，以最不好的运算状况下最高会是7次，怎麽算来的?

很简单

50 >> 25 >> 13 >> 7 >> 4 >> 2 >> 1
总共七次会是最高，当然也是运气好一次就能解决。

那假设10万笔会是几次?

10万 >> 5万 >> 2.5万 >> 1.25万 >> 6250 >> 3125 >> 1563 >> 782 >> 391 >> 196 >> 98

>> 49 >> 25 >> 13 >> 7 >> 4 >> 2 >> 1

18次就可得到答案，这便是使用演算法的好处!

其实考虑过，像我这样的非本科生初期就开始看演算法，似乎对找工作没什麽帮助，不过就当成一种兴趣吧，不然非本科生对於这一块真的是很薄弱。文章分享当然就不会像铁人赛一样每天都会更新。
反正只是初级文章，也不重要啦，哈哈