11.7 Linear Search

Linear Search Algorithm

  • Searches each element in an array sequentially
  • If the search key does not match an element in the array, the algorithm informs the user that the search key is not present
  • If the search key is in the array, the algorithm tests each element until it finds one that matches the search key and returns the index of that element

Linear Search Algorithm (cont.)

  • Consider

    35 73 90 65 23 86 43 81 34 58

  • Searching for 86
    • Algorithm first checks whether 35 matches the search key
    • It does not, so the algorithm checks whether 73 matches the search key
    • Continues moving through the array sequentially, testing 90, then 65, then 23
    • When the program tests 86, which matches the search key, the program returns the index 5
    • If, after checking every array element, the program determines that the search key does not match any element in the array, it returns a sentinel value (e.g., -1)

Linear Search Implementation

  • linear_search linear searches an array of integers
  • Receives the array to search (data) and the search_key
  • The for loop iterates through data’s elements and compares each with search_key
  • Teturns the index of the matching element or -1
In [1]:
def linear_search(data, search_key):
    for index, value in enumerate(data):
        if value == search_key:
            return index
    return -1
In [2]:
import numpy as np
In [3]:
np.random.seed(11)
In [4]:
values = np.random.randint(10, 91, 10)
In [5]:
values
Out[5]:
array([35, 73, 90, 65, 23, 86, 43, 81, 34, 58])
In [6]:
linear_search(values, 23)
Out[6]:
4
In [7]:
linear_search(values, 61)
Out[7]:
-1
In [8]:
linear_search(values, 34)
Out[8]:
8

©1992–2020 by Pearson Education, Inc. All Rights Reserved. This content is based on Chapter 5 of the book Intro to Python for Computer Science and Data Science: Learning to Program with AI, Big Data and the Cloud.

DISCLAIMER: The authors and publisher of this book have used their best efforts in preparing the book. These efforts include the development, research, and testing of the theories and programs to determine their effectiveness. The authors and publisher make no warranty of any kind, expressed or implied, with regard to these programs or to the documentation contained in these books. The authors and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these programs.