二分查找又称为折半查找, 基本思想是对一个有序的列表去检索. 首先将查找值与列表中间位置上的值比较, 如果相等, 则检索成功. 若查找值小, 则在列表前半部分中继续进行二分查找.若查找值大, 则在列表后半部分中继续进行二分查找. 这样, 经过一次比较就缩小一半的查找区间, 如此进行下去, 直到查找成功或查找失败.
这个kata很简单, 用你熟悉的语言(一种)把二分查找, 实现5次.
目标
这个kata有三个独立的目标:
- 当你在写下每种实现的时候, 把你实现过程中的错误也记录下来.
- 你说一下你使用的实现优势是什么, 哪一个最可能进入生产环境, 哪一个最好玩, 哪一个最不容易跑起来?
- 想出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
```