5

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

The problem is, when i enter 7 values array like

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

And search for 66 for example, when

MID = 5

, 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

Where it should be 7 of course.

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

Jonathan Dursi
  • 50,107
  • 9
  • 127
  • 158
Rafael Adel
  • 7,673
  • 25
  • 77
  • 118
  • 1
    Note that binary search isn't always faster than linear searching even though you would really expect it to be. ( http://stackoverflow.com/q/10524032/748858 ) – mgilson Jun 15 '12 at 01:50

1 Answers1

11

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.

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
Jonathan Dursi
  • 50,107
  • 9
  • 127
  • 158