kata02:只有10%的程序员能写好的二分查找

二分查找又称为折半查找, 基本思想是对一个有序的列表去检索. 首先将查找值与列表中间位置上的值比较, 如果相等, 则检索成功. 若查找值小, 则在列表前半部分中继续进行二分查找.若查找值大, 则在列表后半部分中继续进行二分查找. 这样, 经过一次比较就缩小一半的查找区间, 如此进行下去, 直到查找成功或查找失败.

这个kata很简单, 用你熟悉的语言(一种)把二分查找, 实现5次.

目标

这个kata有三个独立的目标:

1. 当你在写下每种实现的时候, 把你实现过程中的错误也记录下来.
2. 你说一下你使用的实现优势是什么, 哪一个最可能进入生产环境, 哪一个最好玩, 哪一个最不容易跑起来?
3. 想出5种方法是很难的, 特别是在想第四种和第五种的时候, 你是怎么突破自我的?

规范

输入int和int数组, 返回也是int(数组中的位置), 如果没查找到返回-1.
chop(int, array_of_int) -> int
这个kata不考性能和效率, 可以假设数组中的元素少于100,000个.

测试数据

这个是我用的测试数据, 你也可以自己构造或者换成适合你使用的语言, 我这里用的是ruby.

def 
    test_chop 
    assert_equal(-1, chop(3, [])) 
    assert_equal(-1, chop(3, [1])) 
    assert_equal(0, chop(1, [1])) 
    # 
    assert_equal(0, chop(1, [1, 3, 5])) 
    assert_equal(1, chop(3, [1, 3, 5])) 
    assert_equal(2, chop(5, [1, 3, 5])) 
    assert_equal(-1, chop(0, [1, 3, 5])) 
    assert_equal(-1, chop(2, [1, 3, 5])) 
    assert_equal(-1, chop(4, [1, 3, 5])) 
    assert_equal(-1, chop(6, [1, 3, 5])) 
    # 
    assert_equal(0, chop(1, [1, 3, 5, 7])) 
    assert_equal(1, chop(3, [1, 3, 5, 7])) 
    assert_equal(2, chop(5, [1, 3, 5, 7])) 
    assert_equal(3, chop(7, [1, 3, 5, 7])) 
    assert_equal(-1, chop(0, [1, 3, 5, 7])) 
    assert_equal(-1, chop(2, [1, 3, 5, 7])) 
    assert_equal(-1, chop(4, [1, 3, 5, 7])) 
    assert_equal(-1, chop(6, [1, 3, 5, 7])) 
    assert_equal(-1, chop(8, [1, 3, 5, 7]))
end
```