• Uncategorized
  • 0

21-Day Challenge Algorithm Learning to Punch Cards – Sequential Search

Hits: 0

Qiuyi community

​🔥Foreword

Recently, the CSDN official learning challenge has rich rewards, and I also signed up to participate in the algorithm track. It is expected to output more than nine classic algorithm articles, including the concept introduction of various classic algorithms and the analysis of related topics to help everyone understand and improve. The content of today’s article is a [sequential search] , and then start the text content.
Event address: CSDN 21-day Learning Challenge

Article directory

Sequential search algorithm analysis

1. Basic Concepts

Sequential search is for any sequence and a given element, compare the given element with the elements in the sequence in turn, until it finds the same element with the given key, or compares all the elements in the sequence with it, if If the same element is not found at this time, the search fails.
Note: The sequence has no repeated elements, otherwise it does not meet the concept of finding the same keyword to stop.

2. Specific cases

1. Problem description

Given an array arr, find keythe position of the value in the array (requires subscripts to start from 1)

2. Step analysis

  1. Use a loop to compare the key value with the elements in the array in turn. If they are equal, return the subscript of the array and add one. If they are not equal, add one to the subscript to continue the comparison.
  2. The diagram is as follows:

3. Code Implementation

Code implementations in different languages ​​are provided here, but the algorithm ideas are the same

1. C++ implementation

int arr[ 8 ] = { 12 , 8 , 11 , 5 , 17 , 19 , 39 , 66 };
     int key = 19 ;
     for ( int i = 0 ; i < 8 ; i++) {
         if (key == arr[ i]) {
             cout << "The position of the element in the array is: " << i + 1 << endl ;
             break ;
        }
    }
    return 0;

If you want to Cimplement it in language, you can directly change the coutstatement to a printfstatement.

2. Java implementation

public  static  void  main ( String[] args ) {
         //First define the array arr and the element to find key 
        int arr[]={ 12 , 8 , 27 , 5 , 17 , 19 , 39 , 66 };
         int key= 39 ;
         //Call the sequential search function to get the position 
        int pos = find(arr,key);
         //Print the position of the array where the element to be found is located System.out 
        .println(pos+ 1 );
    }
    public static int find(int arr[],int key){
        for(int i=0;i<arr.length;i++){
            if(arr[i]==key){
            }
        }
        return  -1 ; // can't find return -1 
    }

Fourth, time complexity analysis

  1. best case

When the value of key is the same as the first element in the array, then it only needs to be executed once, and the time complexity is O(1)

  1. The worst situation

When the value of key is the same as the last element in the array or the same value as key does not exist in the array, then the number of times to be executed is the size of the array: n times, and the time complexity is O(n)

For the time complexity of the algorithm, only the worst case is generally considered, so the time complexity of the sequential search algorithm isO(n)

write at the end

You may also like...

Leave a Reply

Your email address will not be published.