Вопрос по search, fortran, arrays – Бинарный поиск в массиве с использованием Fortran

4

Я использую книгу «Схемы программирования с помощью Schaum» на языке Fortran 77, и приведен пример двоичного поиска с использованием метода группы значений в скобках. Прежде всего, вот код:

    INTEGER X(100)
    INTEGER RANGE
    INTEGER START , FINISH

    PRINT *, 'Number of values ?'
    READ *, N
    DO 10 I = 1, N
        READ *, X(I)
    END DO 

    PRINT *, 'Enter Value'
    READ *, VAL

    START =  1 
    FINISH = N
    RANGE = FINISH - START 
    MID = (START + FINISH) /2

    DO WHILE( X(MID) .NE. VAL .AND. RANGE .NE. 0)
      IF (VAL .GT. X(MID))THEN
        START = MID 
      ELSE 
        FINISH = MID
      END IF
      RANGE = FINISH - START
      MID = (START + FINISH)/2
    END DO 

    IF( X(MID) .NE. VAL) THEN
      PRINT *, VAL, 'NOT FOUND'
    ELSE
      PRINT *, 'VALUE AT' , MID
    END IF
    END

Проблема в том, что когда я ввожу массив из 7 значений, как

2 | 9 | 11 | 23 | 49 | 55 | 66

И искать 66, например, когда

MID = 5

новый MID для следующего цикла становится 6. Но когда он равен 6, он не может быть увеличен для следующего цикла, потому что

MID = (START + FINISH)/2 = (6+7)/2 = 6

Где это должно быть 7 конечно.

Это все еще на 6. И моя программа никогда не дает мне выход конечно. Что мне здесь делать?

Хорошо спасибо. Я проверю это. Rafael Adel
Обратите внимание, что бинарный поиск не всегда быстрее линейного поиска, даже если вы действительно ожидаете, что он будет. (stackoverflow.com/q/10524032/748858 ) mgilson

Ваш Ответ

1   ответ
10

или, может быть, кто-то запутался, когда они перевели его с версии C и пришлось изменить индексацию.

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

Правильная версия устанавливает начало до середины + 1 или конец до середины 1, чтобы исключить середину. Исправленный код, написанный в стиле Fortran 90:

program binarysearch

    implicit none
    integer, allocatable, dimension(:) ::  x
    integer :: range, start, finish, mid
    integer :: i, n, val

    print *, 'Number of values ?'
    read *, N
    allocate( x(N) )

    do i = 1, n
        READ *, x(i)
    end do

    print *, 'Enter Value'
    read *, VAL

    start =  1
    finish = N
    range = finish - start
    mid = (start + finish) /2

    do while( x(mid) /= val .and. range >  0)
      if (val > x(mid)) then
        start = mid + 1
      else
        finish = mid - 1
      end if
      range = finish - start
      mid = (start + finish)/2
    end do

    if( x(mid) /= val) then
      print *, val, 'NOT FOUND'
    else
      print *, 'VALUE AT' , mid
    end if

    deallocate( x )

end program binarysearch
маленький вопрос, это быстрее, чем что-то вроде np.where. я ищу альтернативы, используя f2py.
+1 для Фортрана 90 тоже

Похожие вопросы