[Python Algorithm Series 9] Sequential Search Algorithm

definition

Lookup is defined as: in a set of data elements, determine by a certain method whether the same data element with the given key exists in the set. Generally speaking, if the search is successful, the program will return the location of the data or related information; if the search fails, it will return the corresponding prompt.

The search methods can be divided into two types: the comparative search method and the computational search method.

The comparative lookup method is based on two [data structures] : linear tables and trees. [The object to be looked up (generally a collection]
of data elements/records of the same type ) can also be referred to as a lookup table.[] can also be referred to as a lookup table.[]

Lookup is also divided into static lookup and dynamic lookup.
When the lookup table is statically searched, the program only searches and returns information;

When performing dynamic search, on the basis of static search, operations of adding and deleting data elements in the look-up table are also added.

[Sequential search] is the most basic and simplest of all search methods, and is generally used to search linear tables. It is an algorithm for traversing the query according to the original order of the data in the lookup table. Since the entire lookup table needs to be traversed, the time complexity of sequential lookup is O(n).

For example, as shown in Figure 1, in an array, the sequential search is to search according to the subscript of the data from small to large. At this time, as long as you know the length of the array, you can use a for loop to complete the search. The code inside the for loop depends on the output requirements.

Figure 1: Sequential search

Next, two examples of sequential search are introduced.

[Example 1]
Find the first position of a given element in a known list [1,3,5,4,2,4,6,5,1]. If the given element exists in the list, output its subscript; if not, output -1. The given element of input is of type int.

arr = [1,3,5,4,2,4,6,5,1]
key = int(input()) #input keyword 
for i in range(len(arr)): #traverse the list in order 
    if arr[i] == key:
         print (i)
         break #guarantee  that only the first position is output Break out of the traversal loop 
#Keyword does not exist in the list 
print (-1)

In this program, print(-1) will only be executed when the for loop is terminated naturally. (Natural termination means breaking out of the loop when i>=len(arr), not because break ends the loop.) Therefore, when breaking out of the for loop, we can be sure that there is no element equal to key in the list, so output -1.

[Example 2]
Find a given element in a known list [1,3,5,4,2,4,6,5,1]. Print all occurrences of subscripts for the given element. If the given element does not exist in the array, do not output. The given element of input is of type int.

arr = [1,3,5,4,2,4,6,5,1]
key = int(input()) #input keyword 
for i in range(len(arr)): #traverse the list sequentially 
    if arr[i] == key: #as long as the keyword is equal to the current element, output the current subscript 
        print (i)

Unlike Example 1, there is no break statement in the code of Example 2, which ensures that the position of each element equal to key is output.

In general, search in the order of the data, and the search in order is a matter of course.

Leave a Comment

Your email address will not be published. Required fields are marked *