本文学习内容来自《算法图解》一书及百度百科内容
算法是一组完成任务的指令。任何代码片段都可视为算法。 —— 摘自《算法图解》[^footnote]
以下内容摘自百度百科 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
当我们去思考上面问题,我们是不是这样可以通过地毯式的搜索,去达到我们的目的,例如我们可以从词典的第一页开始找,总能找到“算法”;我们从书的第一页开始翻,在下课之前一定能够翻到146页;或者你给我的范围,我从最小的开始猜,“0,1,2,3,······97,98,99 。对啦!” 我总能猜到你心里想的数字。这种方式称其简单查找。
看到这估计大部分同学已经看懂了二分查找的核心实现思路了。那我们来看看具体的实现过程
这里面大家需要注意一下,二分查找的使用是有硬性的条件约束的,必须满足条件的数据才能够使用二分查找。
首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
为了方便大家学习和调试,这里列出Java 和 python的代码给大家参考。
Java
public static int dichotomy(int[] ints, int item) {
int start = 0;
int end = ints.length - 1;
while (start <= end) {
int mid = (start + end) >>> 2;
int guess = ints[mid];
if (guess == item) {
return mid;
} else if (guess > item) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}python
def dichotomy(list, item):
low = 0
high = len(list) - 1
while low <= high:
mid = (low + high) // 2
guess = list[mid]
if guess == item:
return mid
elif guess > item:
high = mid - 1
else:
low = mid + 1
return None