二进制搜索效率相对于在FORTRAN线性搜索效率(binary search efficiency

这个问题是关于线性搜索与在连续的存储预排序后的数组的二进制搜索的效率的效率...

我有Fortran语言编写的应用程序（77！）。我的部分的代码的一个频繁操作是找到索引在一个数组，使得gx(i) <= xin < gx(i+1) 我现在实现了这个作为一个binary search -遗憾的声明标签和goto -我什么评论相当于statments将使用Fortran 90的...

        i=1
        ih=nx/2
201     continue  !do while (.true.)
           if((xin.le.gx(i)).and.(xin.gt.gx(i+1)))then  !found what we want
              ilow=i+1; ihigh=i
              s1=(gx(ihigh)-xin)/(gx(ihigh)-gx(ilow))
              s2=1.0-s1
              return
           endif
           if(i.ge.ih)then
              goto 202 !exit
           endif
           if(xin.le.(gx(ih))then !xin is in second half of array
              i=ih
              ih=nx-(nx-ih)/2
           else !xin is in first half of array
              i=i+1
              ih=i+(ih-i)/2
           endif
        goto 201  !enddo

然而，今天，我读维基百科上关于二进制搜索，我碰到这个就来了：

Binary search can interact poorly with the memory hierarchy 
(i.e. caching), because of its random-access nature. For 
in-memory searching, if the span to be searched is small, a
linear search may have superior performance simply because 
it exhibits better locality of reference.

我不完全理解这种说法 - 我的印象是，缓存取聚集在一个大的时间（ISH）块，所以如果我们开始在数组的开头，我认为大多数阵列的将是缓存已经（至少，它更将是一个线性搜索），所以我不认为这事。

所以我的问题是，有没有办法知道哪些算法的性能会更好（线性或二进制搜索？）是否有数组大小的边界？我目前使用大小的数组约100元...

对于小数组，这个问题是不是缓存。你是对的：一小阵很可能被快速缓存。

问题是，分支预测可能失败的二进制搜索，因为分支采取或数据相关的方式随意跳过。分支预测失误搪塞CPU流水线。

这种影响可能是严重的。您可以轻松地搜索3〜8元线性需要做一个单一的二进制搜索分支在同一时间（和你需要做多个二进制搜索分支）。确切的盈亏平衡点需要进行测量。

拖延CPU流水线是极其昂贵的。甲的Core i7可以（在3GHz每秒12千兆指令！）退休高达每个时钟周期4点的指令。但是，只有，如果你不拖延。

有免费的分支算法做使用条件，移动CPU指令的二进制搜索。这些算法基本上展开32个搜索步骤和使用CMOV在每个步骤（32个步骤是理论上的最大值）。他们是支免费的，但不是免费的摊位：每下一步的前一个依赖100％，使CPU不能在指令流中冲上去。它必须等待所有的时间。因此，他们不解决这个问题，只能稍微提高它。