繼續(xù)做CodeKata肌稻。
第二個(gè)Kata要求很簡(jiǎn)單：二分查找。現(xiàn)在不懂二分查找的程序員恐怕不多了吧？不過二分查找還有一段趣事。
只有10%程序員能寫對(duì)二分查找
這個(gè)結(jié)論出自著名的《編程珠璣》荤堪，相關(guān)內(nèi)容可以看這里：http://www.csdn.net/article/a/2010-04-23/218099
文中讓我感觸最深的一句話是“ in an age when programmers spend more time plugging libraries together than writing actual code, core algorithmic skills are likely if anything to have declined”，千萬不要成為一個(gè)只會(huì)堆砌庫(kù)的泥瓦工枢赔。
let's rock
當(dāng)然逞力，作為一個(gè)Kata，絕對(duì)不可能只要求二分查找這么簡(jiǎn)單糠爬，作者要求的是寫出5種不同的二分查找寇荧。
前兩種地球人都能想到：遞歸和迭代。
我們的代碼太丑了执隧，放一個(gè)寫完之后Google出來的代碼吧揩抡，大概是我們代碼的一半長(zhǎng)：
function binary_search_iterative(value, a) {
var lo = 0, hi = a.length - 1, mid;
while (lo <= hi) {
mid = Math.floor((lo+hi)/2);
if (a[mid] > value)
hi = mid - 1;
else if (a[mid] < value)
lo = mid + 1;
else
return mid;
}
return -1;
}
對(duì)了户侥，我們用的是JavaScript。
這段代碼的重點(diǎn)是hi = mid - 1和lo = mid + 1峦嗤，這兩句中的+1-1有兩個(gè)作用：避免死循環(huán)以及優(yōu)化性能蕊唐，至于為什么能做到這兩點(diǎn)，請(qǐng)大家自己思考一下~
Kata中給出了一些測(cè)試用例烁设，我們寫了一個(gè)測(cè)試函數(shù)方便使用：
var test = function(fn) {
var test_data = [
[-1, [3, []]],
[-1, [3, [1]]],
[0, [1, [1]]],
[0, [1, [1, 3, 5]]],
[1, [3, [1, 3, 5]]],
[2, [5, [1, 3, 5]]],
[-1, [0, [1, 3, 5]]],
[-1, [2, [1, 3, 5]]],
[-1, [4, [1, 3, 5]]],
[-1, [6, [1, 3, 5]]],
[0, [1, [1, 3, 5, 7]]],
[1, [3, [1, 3, 5, 7]]],
[2, [5, [1, 3, 5, 7]]],
[3, [7, [1, 3, 5, 7]]],
[-1, [0, [1, 3, 5, 7]]],
[-1, [2, [1, 3, 5, 7]]],
[-1, [4, [1, 3, 5, 7]]],
[-1, [6, [1, 3, 5, 7]]],
[-1, [8, [1, 3, 5, 7]]],
]
for (var i in test_data) {
console.log(test_data[i][0] == fn.apply(this, test_data[i][1])) // 把a(bǔ)rray當(dāng)作參數(shù)傳入函數(shù)
}
}
test(binary_search_iterative)
使用的時(shí)候直接test(your_function)就可以了替梨。
兩種搞定，第三種文中給出了提示：用函數(shù)式編程装黑。
函數(shù)式編程
函數(shù)式編程到底是什么呢副瀑？我們看了一些資料，仍然沒有理解恋谭，不過大體上來說糠睡，函數(shù)式編程是一種思想，并不是說一定要用haskell疚颊、scala才能進(jìn)行函數(shù)式編程狈孔，很多語言都可以，就像設(shè)計(jì)模式和語言無關(guān)一樣材义。
函數(shù)式編程水太深均抽，我們找了一些不錯(cuò)的學(xué)習(xí)資料，準(zhǔn)備等學(xué)會(huì)之后再來實(shí)現(xiàn)其掂。
這三本都是很不錯(cuò)的函數(shù)式編程學(xué)習(xí)材料到忽，之所以選擇haskell，是為了逼自己用函數(shù)式編程的思維來編程清寇。不過最近應(yīng)該是沒時(shí)間學(xué)習(xí)了喘漏，先存下來，之后一定會(huì)學(xué)华烟。
我沒有特殊的二分查找技巧
第三種也勉強(qiáng)算搞定吧翩迈，這第四第五種可真是難倒我們了，兩個(gè)人想了兩天也沒搞定盔夜，最后只得作罷负饲。如果大家有想法的話一定要告訴我們啊喂链！
虎頭蛇尾
這個(gè)Kata總覺得不爽返十，似乎是太簡(jiǎn)單了，又似乎是自己會(huì)的太少了椭微，有一種使不上力的感覺洞坑。不過通過這個(gè)Kata記住了一種二分查找的簡(jiǎn)潔實(shí)現(xiàn)方法，還找到了函數(shù)式編程的學(xué)習(xí)資料蝇率，也算有所收獲吧迟杂。
