Binary Search (Recursive)

Use the same binary-search window as the iterative lesson, but pass lo and hi through recursive calls.

Algorithm

Basic Implementation

basic.f90

program search_binary_recursive
    implicit none
    integer :: arr(7) = [1, 3, 5, 7, 9, 11, 13]
    integer :: target
    target = 11
    print '(I0)', search(arr, target, 0, 6)
contains
    recursive integer function search(arr, target, lo, hi) result(pos)
        integer, intent(in) :: arr(7), target, lo, hi
        integer :: mid, value
        if (lo > hi) then
            pos = -1
            return
        end if
        mid = lo + (hi - lo) / 2
        value = arr(mid + 1)
        if (value == target) then
            pos = mid
        else if (value < target) then
            pos = search(arr, target, mid + 1, hi)
        else
            pos = search(arr, target, lo, mid - 1)
        end if
    end function search
end program search_binary_recursive

Complexity

Time: O(log n)
Space: O(log n) call stack

Implementation notes

Keep the explicit control flow. Library shortcuts would hide the state changes this lesson is meant to replay.
The final output is intentionally small and deterministic for cross-language comparison.

execution replay The checked-in replay follows the language-neutral state table for `search-binary-recursive`.

cross-language comparison This Fortran DSA version keeps the same data and final output as every other DSA book in this wave.