本文共 1055 字，大约阅读时间需要 3 分钟。

    二分查找的最大问题在于，数据必须放置在内存中且必须是有序的。 假设我们需要更新内存中数据集；你也许会认为这会极大的影响二分 查找：因为我们必须得对内存中一个巨大的、连续的数组进行更新。 但事实比你想象的要简单，实际上，我们程序所使用的内存片段散布 在物理内存中的各个角落，它们被操作系统的页机制所管理并以一个 连续的内存块的形式展现在我们面前。

    有关搜索的问题，我采用的解决方案是：

1 首先试着使用语言内建的哈希表；

2 如果性能不能让人满意，那么就尝试采用二分查找；

3 只有在前面两步都不能取得令人满意的结果的前提下，我才会考虑 使用更复杂的方法。

    关于循环

为什么我们要将算法中的循环运行到结束处，而不是在检测到了目标 值的时候就退出循环呢？

实际上，我们的代码的行为才是正确的行为；虽说对于该行为的正确 性数学证明已经超出了讨论的范围，但这的却是正确的。 假设我们有一个有着n个元素的数组（n是一个很大的值），那么从该 数组中第一次找到目标的概率是1/n。下一次是2/n，只有当元素的个 数减少到了10到20的时候，一次找到目标的概率才变得有意义，而对 于10到20个元素进行查找需要的只是大概4次循环。当查找失败时（在 大多数的应用中很普遍），那些额外的测试就将变成纯粹的额外开销。

    大规模尺度的搜索使用Postings 

#include
    
     using namespace std;int binaryfind(int x[],int target,int n) {//n为x的个数	int high = n;	int low = -1;	while (high - low > 1) {		int probe = (low + high) >> 1;		/*以前的版本是probe=(high=low)/2 但不安全，某些情况下会溢出*/		/*另一个方法		prode=(low+(high-low)/2) 		*/		if (x[probe] > target)			high = probe;		else			low = probe;	}	if (low == -1 || x[low] != target)		return -1;	else		return low;}int main() {	int x[10] = { 1,2,6,7,8,9,123,456,789,999};	cout << binaryfind(x, 7, 10) << endl;}
    

转载地址：https://www.cnblogs.com/l2017/p/9317845.html 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！