Есть две проблемы, приводящие к тому, что ваша процедура рекурсивного поиска bsearch либо останавливается с нежелательным выводом, либо приводит к ошибке сегментации. Просто следуя логике выполнения вашей программы в приведенных вами примерах, выясните причину:
1) значение присутствует и найдено, нежелательный вывод
Сначала рассмотрим первыйпример, где массив b содержит значение i=5, которое вы ищете (значение и индекс указаны с || в первых двух строках блока кода ниже). Используя нотацию Rn для обозначения n '-го уровня рекурсии, L и H для нижней и верхней границ и x для текущей оценки индекса, данный прогон вашего кода можетвыглядят примерно так:
b(x): 1 1 2 4 |5| 5 6 7 8 10
x: 1 2 3 4 |5| 6 7 8 9 10
R0: L x H
R1: Lx H
R2: L x H
5 found at index 5
5 found at index -1
5 found at index -1
В R0 и R1 тесты b(x).lt.i и b(x).gt.i в bsearch работают так, как задумано, чтобы уменьшить интервал поиска. В R2 выполняется петля do в ветви else, idx присваивается правильное значение, и оно печатается - как предполагалось. Однако , теперь встречается оператор return, который возвращает управление вызывающему программному модулю - в этом случае это первый R1 (!), Где выполнение возобновится после if-else if-else блокировать, выводя таким образом сообщение на экран с начальным значением idx=-1. То же самое происходит по возвращении из R0 в основную программу. Это объясняет (нежелательный) вывод, который вы видите.
2) значение отсутствует, ошибка сегментации
Во-вторых, рассмотрим пример, приводящий к ошибке сегментации. Используя те же обозначения, что и раньше, возможный прогон может выглядеть следующим образом:
b(x): 2 2 3 4 4 6 6 7 8 8
x: 1 2 3 4 5 6 7 8 9 10
R0: L x H
R1: L x H
R2: L x H
R3: LxH
R4: H xL
.
.
.
Segmentation fault: 11
В R0-R2 интервал поиска снова сокращается, как и предполагалось. Однако в R3 логика не работает. Поскольку значение поиска i отсутствует в массиве b, один из тестов .lt. или .gt. всегда будет иметь значение .true., что означает, что тест для low .eq. high для завершения поиска никогда не будет достигнут,С этого момента логика больше не действует (например, high может быть меньше low), и код будет продолжать углублять уровень рекурсии, пока стек вызовов не станет слишком большим и не произойдет ошибка сегментации.
Они объяснили основные логические недостатки в коде. Возможной неэффективностью является использование do -loop для поиска самого низкого индекса, содержащего искомое значение. Рассмотрим случай, когда значение, которое вы ищете, например, i=8, и что оно появляется в последней позиции в вашем массиве, как показано ниже. Предположим далее, что по случайности первое предположение для его позиции - x = high. Это подразумевает, что ваш код будет немедленно переходить к do -циклу, где по сути выполняется линейный поиск почти по всему массиву, чтобы найти окончательный результат idx=9. Несмотря на правильность, предполагаемый двоичный поиск скорее становится линейным поиском, что может привести к снижению производительности.
b(x): 2 2 3 4 4 6 6 7 |8| 8
x: 1 2 3 4 5 6 7 8 |9| 10
R0: L xH
8 found at index 9
Устранение проблем
По крайней мере, вы должны переместить low .eq. highвыполнить тест до начала процедуры bsearch, чтобы рекурсия прекратилась до того, как могут быть определены недопустимые границы (затем вам потребуется дополнительный тест, чтобы увидеть, было ли найдено значение поиска или нет). Кроме того, уведомляйте об успешном поиске сразу после его появления, т. Е. После теста на равенство в вашем do -цикле, или только что упомянутого дополнительного теста. Это по-прежнему не учитывает неэффективность возможного линейного поиска.
Учитывая все это, вам, вероятно, лучше ознакомиться с алгоритмами нахождения "крайнего левого" индекса (например, на Wikipedia или посмотрите на проверенную и протестированную реализацию - оба примера здесь используют итерацию вместо рекурсии, возможно, другое улучшение, но применяются те же принципы) и адаптируют ее к Fortran, который может выглядетькак это (только показывая новый код, ... ссылается на существующий код в ваших примерах):
module mod_search
implicit none
contains
! Function that uses recursive binary search to look for `key` in an
! ordered `array`. Returns the array index of the leftmost occurrence
! of `key` if present in `array`, and -1 otherwise
function search_ordered (array, key) result (idx)
integer, intent(in) :: array(:)
integer, intent(in) :: key
integer :: idx
! find left most array index that could possibly hold `key`
idx = binary_search_left(1, size(array))
! if `key` is not found, return -1
if (array(idx) /= key) then
idx = -1
end if
contains
! function for recursive reduction of search interval
recursive function binary_search_left(low, high) result(idx)
integer, intent(in) :: low, high
integer :: idx
real :: r
if (high <= low ) then
! found lowest possible index where target could be
idx = low
else
! new guess
call random_number(r)
idx = low + floor((high - low)*r)
! alternative: idx = low + (high - low) / 2
if (array(idx) < key) then
! continue looking to the right of current guess
idx = binary_search_left(idx + 1, high)
else
! continue looking to the left of current guess (inclusive)
idx = binary_search_left(low, idx)
end if
end if
end function binary_search_left
end function search_ordered
! Move your routines into a module
subroutine sort(p,q)
...
end subroutine sort
subroutine bubble(n,arr)
...
end subroutine bubble
end module mod_search
! your main program
program main
use mod_search, only : search_ordered, sort, bubble ! <---- use routines from module like so
implicit none
...
! Replace your call to bsearch() with the following:
! call bsearch(A,n,s,low,high)
i = search_ordered(A, s)
if (i /= -1) then
print *, s, 'found at index ', i
else
print *, s, 'not found!'
end if
...
end program main
Наконец, в зависимости от вашего фактического варианта использования, вы можете также рассмотреть возможность использования встроенной процедуры Fortran minloc, избавляя вас от необходимости реализовывать все эти функции самостоятельно. В этом случае это можно сделать, внеся следующие изменения в вашу основную программу:
! i = search_ordered(a, s) ! <---- comment out this line
j = minloc(abs(a-s), dim=1) ! <---- replace with these two
i = merge(j, -1, a(j) == s)
, где j, возвращаемое из minloc, будет самым низким индексом в массиве a, где s может быть найдено, и merge используется для возврата j, когда a(j) == s и -1 в противном случае.