Esta questão é sobre a eficiência de uma pesquisa linear versus a eficiência de uma pesquisa binária para uma matriz pré-ordenada em armazenamento contíguo ...

Eu tenho um aplicativo escrito em fortran (77!). Uma operação freqüente da minha parte do código é encontrar o índice em uma matrizgx(i) <= xin < gx(i+1). Eu atualmente implementei isso como umbinary search - desculpe pelos rótulos das declarações egoto - Eu comentei o que as instruções equivalentes estariam usando fortran 90 ...

<code>        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
</code>

No entanto, hoje, eu estava lendo na Wikipédia sobre pesquisa binária e me deparei com isso:

<code>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.
</code>

Eu não entendo completamente esta afirmação - minha impressão foi que buscas de cache foram reunidas em grandes pedaços (ish) de cada vez, então se começarmos no início da matriz, eu pensei que a maioria da matriz estaria em cache já (pelo menos tanto quanto seria para uma pesquisa linear), então eu não achei que isso importaria.

Então, minha pergunta é, existe alguma maneira de dizer qual algoritmo terá melhor desempenho (busca linear ou binária?) Existe um limite de tamanho de matriz? Atualmente estou usando matrizes de tamanho em torno de 100 elementos ...