Fortran searching
last modified November 14, 2026
Looking for a value in a collection is the other half of sorting, and the
method depends on what the collection allows. An unsorted array can only be
scanned from one end to the other; a sorted array can be halved at every step;
an array of buckets selected by a hash function can go straight to the
right place. Fortran also ships intrinsics that answer the common questions in
one statement, and a character string can be searched for a substring with
index.
This article compares a linear scan and a binary search on the same data,
writes the recursive form and the lower bound that finds where a value would be
inserted, uses findloc, maxloc and friends, builds a
hash table with chaining from derived types, searches text, and finishes with a
binary search over a sorted table of records.
Linear search
A linear search visits the elements one by one until it finds the
value or reaches the end. It makes no demands on the order of the data and
works on any type that can be compared with ==. The cost is
proportional to the position of the value, and a value that is absent costs a
full scan. The function below returns the position or zero and counts the
comparisons in an output argument, so the caller can see the price.
module linear
implicit none
private
public :: find_first, count_value
contains
integer function find_first(a, value, probes) result(pos)
integer, intent(in) :: a(:), value
integer, intent(out) :: probes
integer :: i
probes = 0
pos = 0
do i = 1, size(a)
probes = probes + 1
if (a(i) == value) then
pos = i
return
end if
end do
end function find_first
integer function count_value(a, value, probes) result(n)
integer, intent(in) :: a(:), value
integer, intent(out) :: probes
integer :: i
probes = 0
n = 0
do i = 1, size(a)
probes = probes + 1
if (a(i) == value) n = n + 1
end do
end function count_value
end module linear
program q1
use linear
implicit none
integer :: a(10) = [4, 8, 15, 16, 23, 42, 15, 8, 4, 15]
integer :: p, pos, n
pos = find_first(a, 15, p)
print '(a, i0, a, i0, a, i0)', '15 at position ', pos, &
', probes ', p, ', size ', size(a)
pos = find_first(a, 4, p)
print '(a, i0, a, i0)', '4 at position ', pos, ', probes ', p
pos = find_first(a, 99, p)
print '(a, i0, a, i0)', '99 at position ', pos, ', probes ', p
n = count_value(a, 15, p)
print '(a, i0, a, i0)', '15 occurs ', n, ' times, probes ', p
end program q1
The first 15 sits at position 3 and costs three probes, the 4 at the front costs one, and the missing 99 costs ten, one per element. Counting every 15 also costs ten probes, because the function cannot stop early when it must find all occurrences. The array is deliberately unsorted; a linear search is the only option here, and it is also the right choice for a handful of values, where the set-up of a faster structure would cost more than the scan.
$ gfortran q1.f90 -o q1 $ ./q1 15 at position 3, probes 3, size 10 4 at position 1, probes 1 99 at position 0, probes 10 15 occurs 3 times, probes 10
Binary search
A binary search requires the array to be sorted. It compares the
sought value with the middle element, discards the half that cannot contain it,
and repeats on the remaining half. Two indexes, lo and
hi, mark the part still under consideration; the loop ends when
they cross, which means the value is absent. Every step halves the range, so a
thousand values need at most ten comparisons.
module binsearch
implicit none
private
public :: binary
contains
integer function binary(a, value, probes) result(pos)
integer, intent(in) :: a(:), value
integer, intent(out) :: probes
integer :: lo, hi, mid
probes = 0
pos = 0
lo = 1
hi = size(a)
do while (lo <= hi)
mid = (lo + hi) / 2
probes = probes + 1
if (a(mid) == value) then
pos = mid
return
else if (a(mid) < value) then
lo = mid + 1
else
hi = mid - 1
end if
end do
end function binary
end module binsearch
program q2
use binsearch
implicit none
integer :: a(15) = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29]
integer :: wanted(5) = [1, 15, 29, 8, 100]
integer :: i, pos, p
do i = 1, size(wanted)
pos = binary(a, wanted(i), p)
print '(a, i3, a, i2, a, i0)', 'look for ', wanted(i), &
': position ', pos, ', probes ', p
end do
end program q2
The fifteen values are the odd numbers from 1 to 29. Looking for 1, 15 and 29
costs four, one and four probes, and the missing values 8 and 100 also cost
four, since the search always narrows to an empty range. The middle element is
computed as (lo + hi) / 2, integer division rounding down; with
very large indexes the sum could overflow, and the safer form is
lo + (hi - lo) / 2.
$ gfortran q2.f90 -o q2 $ ./q2 look for 1: position 1, probes 4 look for 15: position 8, probes 1 look for 29: position 15, probes 4 look for 8: position 0, probes 4 look for 100: position 0, probes 4
The recursive form and the lower bound
The same search can be written as a recursive function that receives the two bounds as arguments. It is not faster than the loop and it uses more memory, but it states the halving directly and it is the version found in many textbooks. A more useful relative is the lower bound: the first index whose value is not less than the sought one, or one past the end when every value is smaller. That index is where a new value would be inserted to keep the array sorted, and it is what a sorted container uses for insertion.
module bounds
implicit none
private
public :: rbinary, lower_bound
contains
recursive integer function rbinary(a, value, lo, hi, probes) result(pos)
integer, intent(in) :: a(:), value, lo, hi
integer, intent(inout) :: probes
integer :: mid
if (lo > hi) then
pos = 0
return
end if
mid = (lo + hi) / 2
probes = probes + 1
if (a(mid) == value) then
pos = mid
else if (a(mid) < value) then
pos = rbinary(a, value, mid + 1, hi, probes)
else
pos = rbinary(a, value, lo, mid - 1, probes)
end if
end function rbinary
integer function lower_bound(a, value, probes) result(pos)
integer, intent(in) :: a(:), value
integer, intent(out) :: probes
integer :: lo, hi, mid
probes = 0
lo = 1
hi = size(a) + 1
do while (lo < hi)
mid = (lo + hi) / 2
probes = probes + 1
if (a(mid) < value) then
lo = mid + 1
else
hi = mid
end if
end do
pos = lo
end function lower_bound
end module bounds
program q3
use bounds
implicit none
integer :: a(10) = [2, 4, 4, 4, 7, 9, 11, 15, 15, 20]
integer :: wanted(5) = [4, 8, 1, 20, 21]
integer :: i, pos, p
do i = 1, size(wanted)
p = 0
pos = rbinary(a, wanted(i), 1, size(a), p)
print '(a, i3, a, i2, a, i0)', 'recursive ', wanted(i), &
': position ', pos, ', probes ', p
end do
print *
do i = 1, size(wanted)
pos = lower_bound(a, wanted(i), p)
print '(a, i3, a, i2, a, i0)', 'lower bound of ', wanted(i), &
' is index ', pos, ', probes ', p
end do
end program q3
The array holds a run of three 4s at positions 2 to 4, and the recursive search
reports position 2, the first one it happens to meet. The lower bound is more
precise: for 4 it returns 2, the first of the run; for 8, which is absent, it
returns 6, the position of 9; for 21 it returns 11, one past the last element.
The bounds loop keeps lo < hi and never compares for equality,
which is why it always lands on the first qualifying index.
$ gfortran q3.f90 -o q3 $ ./q3 recursive 4: position 2, probes 2 recursive 8: position 0, probes 3 recursive 1: position 0, probes 3 recursive 20: position 10, probes 4 recursive 21: position 0, probes 4 lower bound of 4 is index 2, probes 4 lower bound of 8 is index 6, probes 3 lower bound of 1 is index 1, probes 4 lower bound of 20 is index 10, probes 3 lower bound of 21 is index 11, probes 3
Array intrinsics
Most searches that a program needs are already written. findloc
returns the position of a value, with back=.true. for the last
one, and zero when nothing matches. maxloc and
minloc return the position of the largest and smallest element.
count, any and all answer questions
about a mask, and pack extracts the elements that satisfy it.
program q4
implicit none
integer :: a(10) = [4, 8, 15, 16, 23, 42, 15, 8, 4, 15]
character(len=8) :: names(5) = [character(len=8) :: 'bob', 'carol', &
'alice', 'dave', 'erin']
print '(a, i0)', 'first 15: ', findloc(a, 15)
print '(a, i0)', 'last 15: ', findloc(a, 15, back=.true.)
print '(a, i0)', 'missing value: ', findloc(a, 99)
print '(a, i0)', 'largest value at ', maxloc(a)
print '(a, i0)', 'smallest at: ', minloc(a)
print '(a, i0)', 'values above 10: ', count(a > 10)
print '(a, l1)', 'any above 40: ', any(a > 40)
print '(a, l1)', 'all positive: ', all(a > 0)
print '(a, 10(i0, 1x))', 'above 10: ', pack(a, a > 10)
print '(a, i0)', 'alice is at: ', findloc(names, 'alice')
print '(a, i0)', 'first 4 in a(4:): ', 4 + findloc(a(4:), 4) - 1
end program q4
The array has 15 at positions 3, 7 and 10, and the two forms of
findloc return 3 and 10; the missing 99 returns zero rather than
an error. The largest value 42 is at position 6 and the smallest 4 at position
1. Six values exceed 10, and pack lists them in order. The
findloc call on a(4:) searches a section, so it counts
from the first element of the section; adding the offset back is the caller's
job, and the last line does exactly that.
$ gfortran q4.f90 -o q4 $ ./q4 first 15: 3 last 15: 10 missing value: 0 largest value at 6 smallest at: 1 values above 10: 6 any above 40: T all positive: T above 10: 15 16 23 42 15 15 alice is at: 3 first 4 in a(4:): 9
A hash table
A hash table computes an index from the key itself and stores the value there. The function that does the computing is the hash function; the array positions are called buckets. Two keys can produce the same bucket, which is a collision, and the table must still tell them apart. The version below uses chaining: every bucket holds a small linked list, and a collision appends to that list. The bucket is found in one step, and the chain holds only the few keys that share it.
module hashes
implicit none
private
public :: table, bucket_count
integer, parameter :: bucket_count = 7
type :: entry
integer :: key = 0
integer :: value = 0
type(entry), pointer :: next => null()
end type entry
type :: bucket
type(entry), pointer :: head => null()
end type bucket
type :: table
type(bucket) :: slot(bucket_count)
integer :: count = 0
contains
procedure :: put => table_put
procedure :: get => table_get
procedure :: show => table_show
end type table
contains
pure integer function bucket_of(key) result(b)
integer, intent(in) :: key
b = mod(abs(key), bucket_count) + 1
end function bucket_of
subroutine table_put(self, key, value)
class(table), intent(inout) :: self
integer, intent(in) :: key, value
type(entry), pointer :: cur, fresh
integer :: b
b = bucket_of(key)
cur => self%slot(b)%head
do while (associated(cur))
if (cur%key == key) then
cur%value = value
return
end if
cur => cur%next
end do
allocate (fresh)
fresh%key = key
fresh%value = value
fresh%next => self%slot(b)%head
self%slot(b)%head => fresh
self%count = self%count + 1
end subroutine table_put
integer function table_get(self, key, found) result(value)
class(table), intent(in) :: self
integer, intent(in) :: key
logical, intent(out) :: found
type(entry), pointer :: cur
found = .false.
value = 0
cur => self%slot(bucket_of(key))%head
do while (associated(cur))
if (cur%key == key) then
found = .true.
value = cur%value
return
end if
cur => cur%next
end do
end function table_get
subroutine table_show(self)
class(table), intent(in) :: self
type(entry), pointer :: cur
integer :: b
do b = 1, bucket_count
write (*, '(a, i0, a)', advance='no') 'bucket ', b, ':'
cur => self%slot(b)%head
do while (associated(cur))
write (*, '(1x, i0, a, i0)', advance='no') cur%key, &
'=>', cur%value
cur => cur%next
end do
print *
end do
end subroutine table_show
end module hashes
program q5
use hashes
implicit none
type(table) :: h
integer :: i, keys(7) = [10, 20, 27, 3, 44, 15, 7]
integer :: value
logical :: found
do i = 1, size(keys)
call h%put(keys(i), keys(i) * 10)
end do
call h%put(27, 999)
print '(a, i0)', 'entries: ', h%count
call h%show()
value = h%get(44, found)
print '(a, i0, a, l1)', 'key 44 -> ', value, ', found ', found
value = h%get(27, found)
print '(a, i0, a, l1)', 'key 27 -> ', value, ', found ', found
value = h%get(50, found)
print '(a, i0, a, l1)', 'key 50 -> ', value, ', found ', found
end program q5
Seven keys spread over seven buckets, and two buckets stay empty while bucket 4 holds 3 and 10 and bucket 7 holds 27 and 20. The second insertion of 27 finds the key in its chain and replaces the value instead of adding a node, so the count stays seven. A lookup for 50 hashes to bucket 2 and walks its single node without finding the key, which is why the answer is false. The number of keys divided by the number of buckets is the load factor; keeping it near one, by growing the bucket array when the table fills, keeps the chains short.
$ gfortran q5.f90 -o q5 $ ./q5 entries: 7 bucket 1: 7=>70 bucket 2: 15=>150 bucket 3: 44=>440 bucket 4: 3=>30 10=>100 bucket 5: bucket 6: bucket 7: 27=>999 20=>200 key 44 -> 440, found T key 27 -> 999, found T key 50 -> 0, found F
Searching text
Character strings have their own searching intrinsics. index(text,
word) returns the position of the first occurrence of a substring and
zero when it is absent, so a loop that advances past each match counts all of
them. scan returns the position of the first character that
belongs to a set, and verify the position of the first character
that does not. These three cover most of the parsing that a program does by
hand in other languages.
program q6
implicit none
character(len=*), parameter :: text = &
'the cat sat on the mat, the end of the tale'
integer :: start, pos, n
start = 1
n = 0
do
pos = index(text(start:), 'the')
if (pos == 0) exit
pos = pos + start - 1
n = n + 1
print '(a, i0)', 'the starts at ', pos
start = pos + len('the')
end do
print '(a, i0)', 'occurrences: ', n
print '(a, i0)', 'first vowel at: ', scan(text, 'aeiou')
print '(a, i0)', 'first character outside letters: ', &
verify(text, 'abcdefghijklmnopqrstuvwxyz ')
print '(a, i0)', 'index of cat: ', index(text, 'cat')
print '(a, i0)', 'index of dog: ', index(text, 'dog')
print '(a, l1)', 'text ends with tale: ', text(len_trim(text) - 3:) == 'tale'
end program q6
The word the occurs four times, at positions 1, 16, 25 and 36.
The loop adds the length of the word to the last position before searching
again, which is what prevents the same occurrence from being found twice.
scan reports 3, the e of the first word, and
verify reports 23, the comma after mat, the first
character that is not a letter or a blank. A missing word gives zero, which is
easy to test, and the comparison at the end confirms that the text ends with
tale.
$ gfortran q6.f90 -o q6 $ ./q6 the starts at 1 the starts at 16 the starts at 25 the starts at 36 occurrences: 4 first vowel at: 3 first character outside letters: 23 index of cat: 5 index of dog: 0 text ends with tale: T
Searching a sorted table
The same binary search works on an array of records when the records are ordered by the key that is searched. The function below compares the name component of the middle record with the wanted name, and character comparison runs from left to right with blanks sorting before letters. Because the dummy name is declared with the same length as the component, both sides are padded the same way and the comparison is consistent.
module directory
implicit none
private
public :: record, find_name
type :: record
character(len=12) :: name = ''
character(len=12) :: city = ''
integer :: extension = 0
end type record
contains
integer function find_name(list, name, probes) result(pos)
type(record), intent(in) :: list(:)
character(len=12), intent(in) :: name
integer, intent(out) :: probes
integer :: lo, hi, mid
probes = 0
pos = 0
lo = 1
hi = size(list)
do while (lo <= hi)
mid = (lo + hi) / 2
probes = probes + 1
if (list(mid)%name == name) then
pos = mid
return
else if (list(mid)%name < name) then
lo = mid + 1
else
hi = mid - 1
end if
end do
end function find_name
end module directory
program q7
use directory
implicit none
type(record) :: staff(6) = [ &
record('alice', 'bratislava', 101), &
record('bob', 'kosice', 102), &
record('carol', 'zilina', 103), &
record('dave', 'nitra', 104), &
record('erin', 'trnava', 105), &
record('frank', 'presov', 106)]
character(len=12) :: wanted(4) = [character(len=12) :: &
'alice', 'carol', 'frank', 'zoe']
integer :: i, pos, p
do i = 1, size(wanted)
pos = find_name(staff, wanted(i), p)
if (pos > 0) then
print '(a, a, a, a, i0, a, i0)', trim(wanted(i)), &
' works in ', trim(staff(pos)%city), ', extension ', &
staff(pos)%extension, ', probes ', p
else
print '(a, a, i0)', trim(wanted(i)), &
' is not in the list, probes ', p
end if
end do
end program q7
Alice is found in two probes, carol in one because she sits at the middle of six records, and frank in three, while zoe ends the search after three probes with no match. The failed lookup returns zero, and the caller must check it before reading a record. A directory of ten thousand names would still need about fourteen probes, which is the point of keeping the table sorted when lookups are frequent and insertions are rare.
$ gfortran q7.f90 -o q7 $ ./q7 alice works in bratislava, extension 101, probes 2 carol works in zilina, extension 103, probes 1 frank works in presov, extension 106, probes 3 zoe is not in the list, probes 3
Next steps
The sorting article produces the sorted arrays
that binary search needs, and the
binary trees article shows a structure
that keeps values ordered while they are inserted, so no separate sort is
needed. The linked lists article explains
the node and pointer mechanics behind the hash chains, and the
array intrinsics article covers
findloc, pack and the mask functions in more detail.
The strings article treats character handling
as a subject of its own.
Source
Fortran 2018 standard (J3/18-007r1)
Fortran-lang: learning resources
In this article we have searched an array linearly and counted the probes, used
binary search on a sorted array, written the recursive version and the lower
bound, used findloc, maxloc, count,
any and pack, built a hash table with chaining from a
bucket type and a node type, found every occurrence of a word with
index, and searched a sorted table of records by name. The
previous article, Fortran sorting, explains how
those arrays and records are put in order.
Author
List all Fortran tutorials.