二分查找是基本算法,但是据统计只有10%的程序员可以写出没有bug的代码。出错的原因主要集中在对边界值得选择和判定条件上,一不小心就可能导致超出边界或者死循环的情况。这里作如下总结:

标准版二分查找:
在有序(非降序)数组中查找一个target值,数组中元素没有重复,找到target则返回该元素对应的index,找不到则返回-1。

注意1:如果是start < end,那么当target等于num时,会找不到该值。 注意2:因为num > target, 所以如果有num == target, index一定小于mid,能不能写成end = mid呢?举例来说:num = {1, 2, 5, 7, 9}; 如果写成end = mid,当循环到start = 0, end = 0时(即num = 1, num = 1时),mid将永远等于0,此时end也将永远等于0,陷入死循环。也就是说寻找target = -2时,程序将死循环。 447 more words