Binary Search algorithm random array

Question

I don't understand why the recursive function always gives me zero result, even if I put values inside the array. it seems that size (a) == 0

recursive function binarySearch_R (a, value) result (bsresult)
real, intent(in) :: a(6), value
integer          :: bsresult, mid

mid = size(a)/2 + 1
if (size(a) == 0) then
    bsresult = 0        ! not found
else if (a(mid) > value) then
    bsresult= binarySearch_R(a(:mid-1), value)
else if (a(mid) < value) then
    bsresult = binarySearch_R(a(mid+1:), value)
    if (bsresult /= 0) then
        bsresult = mid + bsresult
    end if
else
    bsresult = mid      ! SUCCESS!!
end if
end function binarySearch_R

program hji
read*, a
read*, value
print*, binarySearch_R
end program hji

Answer 1

Chapter 1: The dangers of implicit typing

The first thing I strongly recommend you do is to include the line

implicit none

after the program line. This will suppress implicit typing, and the resulting errors will give you some useful insight into what is happening.

If you did that, you'd get an error message:

$ gfortran -o binsearch binsearch.f90
binsearch.f90:23:12:

     read*, a
            1
Error: Symbol ‘a’ at (1) has no IMPLICIT type
binsearch.f90:27:25:

     print*,binarySearch_R
                     1
Error: Symbol ‘binarysearch_r’ at (1) has no IMPLICIT type
binsearch.f90:24:16:

     read*, value
            1
Error: Symbol ‘value’ at (1) has no IMPLICIT type

It doesn't matter that a, value, and binarySearch_R were defined in the function. As the function is not part of the program block, the program doesn't know what these are.

With implicit typing active, it simply assumed that all three are simple real variables. (The type depends on the first letter of the variable name, i through n are integer, everything else is real)

Because this implicit typing can so easily hide coding errors, it's strongly, strongly suggested to always switch it off.

Which also means that we have to declare the variables a and value in the program:

program hji
    implicit none
    real :: a(6), value
    ...
end program hji

Chapter 2: How to introduce a function to the program?

So how does the program get access to the function? There are four ways:

1. The best way: Use a module

    module mod_binsearch
        implicit none
    contains
        recursive function binarySearch_R (a, value) result (bsresult)
            ...
        end function binarySearch_R
    end module mod_binsearch
   
    program hji
        use mod_binsearch
        implicit none
        real :: a(6), value
        ...
    end program hji
   

   Note that the use statement has to be before the implicit none. This method leaves the function separate, but callable. It automatically checks that the parameters (that's something we'll be coming to in a bit) are correct.

2. Have the function contained in the program.

   Between the final line of code of the program and the end program statement, add the keyword contains, followed by the function code (everything from recursive function ... to end function ...).

   This is the quick-and-dirty method. You have to be careful with this method as the function will automatically have access to the program's variables unless there's a new variable with that name declared inside the function.

3. The convoluted way: Interfaces

   Create an interface block in the declaration section of your program's source code, and repeat the interface information in there.

   This still allows the compiler to check whether the function is invoked correctly, but it's up to you to ensure that this interface block is correct and matches the actual implementation.

4. The really, really ugly way: Declare it like a variable, invoke it like a function.

   Please don't do that.

Chapter 3: Calling a function

When you call a function, you have to use the parentheses and give it all the parameters that it expects. In your case, you need to type

print *, binarySearch_r(a, value)

Chapter 4: Dynamic arrays as dummy parameters

In the successive recursive calls to the function, the array gets smaller and smaller. But the dummy parameter is always the same size (6). Not only will this interfere with your algorithm, but this can also lead to dangerously undefined memory access.

Fortunately, specially for intent(in) dummy parameters, you can use dynamic arrays:

recursive function binarySearch_R(a, value)
    real, intent(in) :: a(:), value

The single colon tells the compiler to expect a one-dimensional array, but not the length of it. Since you're already using size(a), it should automatically work.

Answer 2

Too long for a comment, but not an answer (and to any Fortran experts reading this, yes, there are one or two places where I gloss over some details because I think they are unimportant at this stage) ...

The way the code is written does not allow the compiler to help you. As far as the compiler is concerned there is no connection between the function and the program. As far as the program is concerned a is, because you haven't told the compiler otherwise, assumed to be a real scalar value. The a in the program is not the same thing as the a in the function - there is no connection between the function and the program.

The same is true for value.

The same is true for binarysearch_r - and if you don't believe this delete the function definition from the source code and recompile the program.

So, what must you do to fix the code ?

First step: modify your source code so that it looks like this:

program hji
... program code goes here ...
contains
    recursive function binarySearch_R (a, value) result (bsresult)
    ... function code goes here ...
    end function binarySearch_R
end program hji

This first step allows the compiler to see the connection between the program and the function.

Second step: insert the line implicit none immediately after the line program hji. This second step allows the compiler to spot any errors you make with the types (real or integer, etc) and ranks (scalar, array, etc) of the variables you declare.

Third step: recompile and start dealing with the errors the compiler identifies. One of them will be that you do not pass the arguments to the function so the line

print*, binarySearch_R

in the program will have to change to

print*, binarySearch_R(a, value)