如果你要在字典中查找一个以O开头的单词，你从头开始翻页，直到O开头的那块儿。这就是简单查找，也叫顺序查找。你可能会想，谁会这么傻？一本牛津双解词典2600多页，谁会闲着没事翻书翻到手抽筋儿呀。
关爱智障的眼神
对呀，大家都不会这么做，咱会直接打开字典中间看看是否是以O开头的，要是不是的话就能排除掉一半，然后再继续翻。这就类似于二分查找。
机智
二分查找是一种算法，其输入是一个有序的元素列表（必须有序）。如果要查找的元素包含在列表中，二分查找返回其所在的位置；否则返回null。
不举例子的讲课都是耍流氓：假如你和胖友一起猜玩数字的游戏，游戏规则是酱紫的：你的胖友随机想一个1-100之间的数字，然后你必须不超过10次就猜中这个数字，每次猜测之后，对方会说小了/大了/对了，否则就得接受“爱”的惩罚。
好，规则确立，咱们来捋一捋过程。
首先，有100个数。
1-100
假设你从1开始依次往上猜，猜测的过程会是这样子的：
简单查找 - 从1开始依次向上猜
这是简单查找，每次猜测都只能排除一个数字，如果对方想的是99，你得猜99次才能猜到！
下面是一种更简单的算法，从50开始猜，假设对方想的数字是57，虽然猜小了，但是排除掉了一半的数字！
接下来你再猜75，大了，那余下的数字又排除了一半。如此循环知道猜中数字，这就是二分查找。每次猜测排除的数字个数如下：
二分查找 - 每次排除的个数
不管对方心里想的是哪个数字，你都能在7次之内猜到，因为每次猜测都将排除很多数字！
二分查找与简单查找的对比：
假如你要再包含 240 000 个单词的字典中查找一个单词，如果要查找的单词位于字典末尾，使用简单查找将需要 240 000 步；使用二分查找，每次排除一半的单词，知道最后只剩下一个单词。
二分查找处理 240 000 个数据
只需要18步！
一般而言，对于包含n个元素的列表，用二分查找最多需要 log n 步，而简单查找需要 n 步。这就是涉及到下一篇的知识 - 算法性能分析 - 用大O表示法讨论时间复杂度。
基本思想：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
复杂度分析：最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；
折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》
啊，不好意思，忘了加代码。源书中给出的是Python的例子，我会自己写一个C语言和Java的版本出来以供学习。由于我本身对C语言和Java没有太深入的了解，如果有bug或者更优雅的代码请告知我。共同学习，共同进步。
大佬求带
Python 二分查找代码
# 二分查找函数
def binary_search(list, item):
low = 0
high = len(list) -1
while low <= high:
mid = (low + high) / 2
guest = list[mid]
if guest == item:
return mid
if guest > item:
high = mid - 1
else:
low = mid + 1
return None
my_list = [1, 3, 5, 7, 9]
print binary_search(my_list, 3)
print binary_search(my_list, -1)
C 二分查找函数
#include <stdio.h>
int binary_search(int list[], int item, int len)
{
int low = 0, high = len - 1;
int mid, guest;
while (low <= high)
{
mid = (low + high) / 2;
guest = list[mid];
if (guest == item)
return mid;
if (guest > item)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
int main(void)
{
int my_list[] = {1, 3, 5, 7, 9};
int len = sizeof(my_list) / sizeof(my_list[0]);
int a = binary_search(my_list, 3, len);
printf("%d\n", a);
return 0;
}
注：图片均来源于互联网
网友评论