使用Fortran的数组问题二进制搜索 [英] Binary search in array issue using Fortran

问题描述

我使用绍姆的编程Fortran 77的书的大纲，并有关于使用值法的包围组二进制搜索的例子。首先，这里的code：

I'm using Schaum's Outline of Programming With Fortran 77 book, and there's an example about binary search using bracketing group of values method. First of all here's the code :

    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 values​​数组像

The problem is, when i enter 7 values array like

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

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

和搜索66，例如，当

MID = 5

，为下一个循环的新的MID变为6。但是当它是6，也不能得到增加为下一个循环，因为

, the new MID for the next loop becomes 6 . But when it's 6, it can't get incremented for the next loop because

= MID（START + FINISH）/ 2 =（6 + 7）/ 2 = 6

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

当它应该是当然的7。

它仍然6.我的计划从来没有给我，当然的输出。
我该怎么办吗？

It still on 6. And my program never give me an output of course. What shall I do here ?

推荐答案

这只是一个错字，或者当他们从一个C版本翻译它，不得不改变索引。一个人弄糊涂了。

This is just a typo, or maybe someone got confused when they translated it from a C version and had to to change indexing.

在循环中的关键不变的是价值，如果它在列表中，必须落在阵列中从某个地方开始的索引来完成，具有包容性。但是，一旦你已经排除中旬，应采取淘汰之列。但它不是在这里，所以列表总是太长，你碰到你看到的问题。

The key invariant in the loop is that the value, if it's in the list, must fall in the array somewhere from indices start to finish, inclusive. But once you've excluded mid, it should be taken out the list. But it's not here, so the list is always too long and you run into the problem you see.

有一个正确的版本集开始中旬+ 1，或完成中期-1，排除中旬。修正后code，写的Fortran 90的风格：

A correct version sets start to mid+1, or finish to mid-1, to exclude mid. The corrected code, written in a Fortran 90 style:

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

这篇关于使用Fortran的数组问题二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！