Searching

Binary Search (Iterative)

On a sorted array, narrow the [lo, hi] window by halving it each step until arr(mid) equals the target or the window is empty. Demonstrates the "discard half the search space" invariant.

Algorithm

Basic Implementation

basic.f90 
program binary_search
    implicit none
    integer :: arr(7) = [1, 3, 5, 7, 9, 11, 13]
    integer :: target, lo, hi, mid, result
    target = 11
    lo = 1
    hi = 7
    result = -1
    do while (lo <= hi)
        mid = lo + (hi - lo) / 2
        if (arr(mid) == target) then
            result = mid
            exit
        end if
        if (arr(mid) < target) then
            lo = mid + 1
        else
            hi = mid - 1
        end if
    end do
    print '(I0)', result
end program binary_search

The pinned run searches for 11 in [1, 3, 5, 7, 9, 11, 13]. The diagrams highlight the inclusive [lo, hi] window and each midpoint.

Step 1 - First midpoint is too small

lo = 0, hi = 6, mid = 3, and arr[3] = 7 is below target 11.

Probe 1 keeps the right half.i0i1i2i3i4i5i6135791113lomidtargethi

Step 2 - Window narrows to the right

Because 7 < 11, set lo = 4 and keep hi = 6.

After discarding indexes 0 through 3.i0i1i2i3i4i5i6135791113discarddiscarddiscarddiscardlomidhi

Step 3 - Second midpoint matches

Now mid = 5 and arr[5] = 11, so the algorithm returns index 5.

Probe 2 finds target 11 at index 5.i4i5i6return911135lomid == targethiindex

Complexity

  • Time: O(log n)
  • Space: O(1)

Implementation notes

  • Fortran: integer division on positive (hi - lo) is already truncated, so (hi - lo) / 2 is the midpoint offset. Do not call a library bisect; the goal here is zero external dependencies.
  • The replay highlights the [lo, hi] window, mid, and which branch (left half / right half / match) the step takes.
inclusive bounds `lo` and `hi` are both inclusive; the loop runs while `lo <= hi`.
overflow-safe midpoint `mid = lo + (hi - lo) / 2` avoids `(lo + hi)` overflow on large inputs.