Write in front: the blogger is a real combat development after training into the cause of the “hill pig”, nickname from the cartoon “Lion King” in “Peng Peng”, always optimistic, positive attitude towards things around. My technical path from Java full stack engineer all the way to big data development, data mining field, now there are small achievements, I would like to share with you what I have learned in the past, I hope to help you on the way of learning. At the same time, the blogger also wants to build a perfect technical library through this attempt. Any anomalies, errors and matters needing attention related to the technical points of the article will be listed at the end, and everyone is welcome to provide materials in various ways.

  • Please criticize any mistakes in the article and revise them in time.
  • If you have any questions you would like to discuss or learn, please contact me at [email protected].
  • The style of the published article varies from column to column, and all are self-contained. Please correct the deficiencies.

A series of classical algorithms: Sequential Search (with video explanation)

Keywords: classical algorithm, search algorithm, element search, order search, algorithm practice \

The article directories

What is an algorithm

This column is a sub-column of “Hand Tearing Algorithms” : “Classic Algorithms”, which will tell about some classic algorithms and analyze them. Before we do that, we need to understand what an algorithm is and what kind of problem it can solve.

1. Definition of the algorithm

. The following is a classic textbook. The Introduction to Algorithms, the contents of the opening.

Informally, an algorithm is any well-defi Ned computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.

As you can see, any well-defined computational process can be called an algorithm, which takes a value or set of values as input and produces a value or set of values as output. So an algorithm can be described as a series of computational steps that turn input into output. Such generalizations are more standard and abstract, in fact, it is clear steps to solve the problem. Because it is executed in a computer, it is usually represented by pseudo-code first, clearly expressing ideas and steps, so that when it is really executed, different languages can be used to achieve the same effect. In a nutshell, algorithms are tools for solving problems. When describing an algorithm, we focus on the inputs and outputs. In other words, once the raw data and the resulting data are described clearly, then what the algorithm does is clear. When we design an algorithm, we also need to know what we have and what we want, as you will see in later articles.

2. Supplementary concepts

  • The data structure

Algorithms are often associated with data structures because different data structures can be used to store data for the same problem (for example, sorting), and the corresponding algorithms can vary widely. Therefore, in the whole learning process, it will also involve the use of various data structures. Common data structures include arrays, heaps, stacks, queues, linked lists, trees, and so on.

  • Efficiency of the algorithm

After the design of an algorithm is completed, it is necessary to evaluate the implementation of the algorithm. A good algorithm can greatly save running resources and time. There is no need to be too specific in the evaluation. After all, the amount of data is uncertain, and an order of magnitude is usually determined based on the amount of data, usually using the concepts of time complexity and spatial complexity.

  • Time complexity

The frequency with which basic operations in an algorithm are repeated is usually called the time complexity of the algorithm. The basic operations in the algorithm generally refer to the statements in the deepest loop of the algorithm (assignment, judgment, four operations and other basic operations). We can call the time frequency T(n), which is proportional to the number of statements executed in the algorithm. Where n is called the size of the problem and in most cases is the amount of input data. For each piece of code, it can be converted to a constant or function expression related to n, called f(n). If we add up the time spent on each piece of code, we can get an expression describing the time complexity. We can determine the time complexity by reserving the largest part of magnitude after merging, which is called O(f(n)), where O is the order of magnitude. Common time complexities are (from lowest to highest) : O(1), O(log ⁡ 2n \log _{2} nlog2n), O(n), O(n log ⁡ 2n \log _{2} n nlog2n), O(n 2n ^{2} n2), O(n 3 n^{3} n3), O(2n 2 ^ {n} 2 n), O (n!) .

  • Spatial complexity

The memory capacity required by the program from the beginning to the end, that is, the maximum amount of space required during the entire process. To evaluate the algorithm itself, the space taken up by the input data is not considered, but rather how many additional temporary variables or storage structures need to be defined while the algorithm is running. For example, if two elements need to be swapped with a temporary variable, the space complexity is O(1).

  • Pseudocode convention

The pseudo-code is used to describe the steps performed by the algorithm, which is not specific to a particular language. For clarity and standardization, there are some conventions: Indentation: indicates block structures, such as loop structures or selection structures, and indentation indicates that this part is in the structure. Loop counter: For loop structures, the value of the counter should be the first value out of bounds when the loop terminates. To: increases the value of the loop counter. Downto: decreases the value of the loop counter. By: The value of the loop counter defaults to 1, and can be used when greater than 1. Variables are locally defined by default. Array element access: Through the “array name [subscript]” form, in pseudocode, the subscript starts at 1 (“A[1]” represents the first element of array A). Subarrays: use “…” To represent A range in the array, for example, “A[I… j]” represents A subarray from the ith to the JTH elements. Objects and Attributes: Composite data is organized into objects, such as linked lists containing next and stored data, using “object name + dot + attribute name”. Special value NIL: indicates that the pointer does not point to any object. For example, the binary tree node has no children. The information about the left and right children can be considered NIL. Return: Returns to the call point of the calling procedure, allowing multiple values to be returned in pseudocode. And and OR: The and operation is short-circuited by default, meaning that if the result of the expression can already be determined, no other condition will be judged or executed.

Second, sequential search

1. Introduction to element lookup

Search is also known as retrieval. The main purpose of an algorithm is to find elements in a data structure that satisfy a given condition (take equivalent matching as an example). If an element that meets the condition is found, the search succeeds; otherwise, the search fails. When searching, there will be relative matching algorithm for different data structure and element set state, and the preconditions of the algorithm should be paid attention to when using it. In the article related to element search, only one data item is discussed in the data element, that is, the key is the value of the corresponding data element, corresponding to the specific data structure, which can be understood as a one-dimensional array.

  • In order to find

Also known as linear search, is the simplest search method. Start from one side of the array and compare the elements one by one. If they are the same as the given element to be searched, the search succeeds. If no matching element is found after the scan is complete, the search fails.

  • Binary search

Also known as binary search, is a relatively high efficiency search method. The premise of using this algorithm is that elements have been ordered, because the core idea of the algorithm is to narrow the search range as soon as possible, which needs to ensure that there is no element omission in the narrow range. Article Portal: a literary classic algorithm series: Split search (with video at the end).

  • An index lookup

Index search is mainly divided into basic index search and block search. The core idea is that for the disordered data set, the index table is established first, so that the index table is ordered or block ordered, and the method of sequence search and index search is combined to complete the search. Article Portal: A Classic Algorithmic literature series: Index Search

2. Search in sequence

  • The input

A sequence of n numbers, usually stored directly in an array, can be in any order. Element key to be found.

  • The output

Found successfully: Returns the number of the element’s location. Failed to find: Returns -1 or a custom failed identifier.

  • Algorithm that

The algorithm simply scans one end of the array and compares each element until it finds the location or scans all the elements.

  • Algorithm process

The following image is from the data Structure Tutorial6The elements:



iFor a variable that controls the index subscript, starting from the first element and moving backwards.

Each time the element in the corresponding position in the set is taken out, and the element to be foundkeyCompare, and return the logical ordinal number if equal.

If the entire collection scan is complete (by comparing I to the collection length) and is not found, the search is considered to have failed

3. The pseudo code

Sequential lookup directly uses the loop structure to iterate through the collection. Each element is compared with the key, and if it is equal, the loop ends prematurely. The pseudo-code is shown as follows:

i = 1
while i <= A.length
    if A[i] == key
        return i
    i++
return -1
Copy the code

Third, algorithm practice

1. Algorithm implementation

  • Input data: A = {11,34,20,10,12,35,41,32,43,14}, key = 41
  • Java source code

Note the difference between source code and pseudocode. See the concepts supplement at the beginning of this article.

public class SequentialSearch {

    public static void main(String[] args) {
        // input data
        int[] a = {11.34.20.10.12.35.41.32.43.14};
        int key = 41;
        // Call the algorithm and print the result
        int result = search(a, key);
        System.out.println(result);
    }

    private static int search(int[] a,int key) {
        // Initialize variables
        int i = 0;
        // Loop through the array
        while (i < a.length){
            // Compare elements in the collection to keys
            if (a[i] == key){
                // Find the target element and return early
                return i + 1;
            }
            // Each time the index subscript moves back
            i++;
        }
        // If the inner return is not raised at the end of the loop, -1 is returned
        return -1; }}Copy the code
  • The execution result

  • Output data: 7

2. Time complexity

  • Worst-case scenario

The worst case is that the whole set is completely traversed and the target key is not found. In this case, the loop is completely executed and the number of times of loop execution is related to N, so the time complexity is O(n).

  • Best-case scenario

The best case is when you find the element the first time, and the time is constant O(1).

  • On average

Combining the two cases, the time complexity of sequential search is O(n), which is a slow search algorithm.

3. Space complexity

Since the algorithm does not change the original set of elements and only needs an extra variable to control index changes, the spatial complexity is constant: O(1).