相关疑难解决方法(0)

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

我有一个用fortran编写的应用程序(77!).我的部分代码的一个常见操作是在数组中找到索引gx(i) <= xin < gx(i+1).我目前已经实现了这个binary search- 对于声明标签而言goto- 并且- 我已经评论了使用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 …