Этот вопрос касается эффективности линейного поиска и эффективности двоичного поиска предварительно отсортированного массива в непрерывном хранилище ...

У меня есть заявление, написанное на фортране (77!). Одна из частых операций для моей части кода - найти индекс в массиве так, чтобыgx(i) <= xin < gx(i+1), В настоящее время я реализовал это какbinary search - извините за ярлыки заявления иgoto - Я прокомментировал, что эквивалентные оценки будут использовать 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>

Однако сегодня я читал в Википедии о бинарном поиске и наткнулся на это:

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

Я не совсем понимаю это утверждение - у меня сложилось впечатление, что выборки из кеша собирались в большие (ish) порции за раз, поэтому, если мы начнем с начала массива, я подумал, что большая часть массива будет в кеше уже (по крайней мере, столько, сколько было бы для линейного поиска), поэтому я не думал, что это будет иметь значение.

Итак, мой вопрос, есть ли способ определить, какой алгоритм будет работать лучше (линейный или двоичный поиск?) Есть ли граница размера массива? В настоящее время я использую массивы размером около 100 элементов ...