6.6: Searching Arrays

Last updated
Save as PDF

Page ID: 10693

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Overview

Linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.^[1]

Discussion

Finding a specific member of an array means searching the array until the member is found. It’s possible that the member does not exist and the programmer must handle that possibility within the logic of his or her algorithm.

“The linear search is a very simple algorithm. Sometimes called a sequential search, it uses a loop to sequentially step through an array, starting with the first element. It compares each element with the value being searched for, and stops when either the value is found or the end of the array is encountered. If the value being searched for is not in the array, the algorithm will search to the end of the array.”^[2]

Two specific linear searches can be made for the maximum (largest) value in the array or the minimum (smallest) value in the array. Maximum and minimum are also known as max and min. Note that the following max and min functions assume an array size >= 1.

Pseudocode

Function Main
    Declare Integer Array ages[5]
    Declare Integer maximum
    Declare Integer minimum
    
    Assign ages = [49, 48, 26, 19, 16]

    Assign maximum = max(ages)
    Assign minimum = min(ages)

    Output "Maximum age is: " & maximum
    Output "Minimum age is: " & minimum
End

Function max (Integer Array array)
    Declare Integer maximum
    Declare Integer index
    
    Assign maximum = array[0]
    For index = 1 to Size(array) - 1
        If maximum < array[index] 
            Assign maximum = array[index] 
        End 
    End 
Return Integer maximum 

Function min (Integer Array array) 
    Declare Integer minimum 
    Declare Integer index 

    Assign minimum = array[0] 
    For index = 1 to Size(array) - 1 
        If minimum > array[index]
            Assign minimum = array[index]
        End
    End
Return Integer minimum

Output

Maximum age is: 49
Minimum age is: 16

Key Terms

linear search: Using a loop to sequentially step through an array.

maximum: Aka max or the largest member of an array.

minimum: Aka min or the smallest member of an array.

References

cnx.org: Programming Fundamentals – A Modular Structured Approach using C++
Wikiversity: Computer Programming

Wikipedia: Linear search ↵
Tony Gaddis, Judy Walters, and Godfrey Muganda, Starting Out with C++ Early Objects Sixth Edition (United States of America: Pearson – Addison Wesley, 2008) 559. ↵