Binary search in array issue using Fortran

Question

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 ?

Note that binary search isn't always faster than linear searching even though you would really expect it to be. ( stackoverflow.com/q/10524032/748858 ) — mgilson
– mgilson, Commented Jun 15, 2012 at 1:50

Jonathan Dursi · Accepted Answer · 2012-06-15 00:39:19Z

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

edited Jun 15, 2012 at 0:39

answered Jun 15, 2012 at 0:33

Jonathan Dursi

51.1k10 gold badges131 silver badges160 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

George Pamfilis Over a year ago

small question is this faster than something like np.where. i am looking for alternatives by using f2py.

MechEng Over a year ago

This algorithm accesses the array "x" below the lower bound if val<x(1). Better add a bounds check at the beginning.

Collectives™ on Stack Overflow

Binary search in array issue using Fortran

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related