Linear Search/선형 검색

배열에서 데이터를 검사하는 방법중 하나인 선형 검색 또는 순차 검색으로 불리는 방법은 배열에서 데이터를 찾는 가장기본적인 방법이지만 확실하게 모든 요소를 검색할수 있고 정렬되지 않은 배열도 검색할수 있다는점이 장점이다.

말그대로 순서대로 배열을 검색하는 방법인데 배열의 처음 요소 부터 배열의 끝 요소 까지 반복하며 데이터를 찾습니다

반복문을 사용하여 구현합니다.

 

while문 사용

int linear_search_while(const int arr[], int n , int key){ // while syntax
    int i = 0;
    while(true){
        if(i == n){
            return -1;
        }
        if(arr[i] == key){
            return i;
        }
        i++;
    }
}

for 문 사용

int linear_search_for(const int arr[], int n, int key){ // for syntax
    for(int i = 0; i < n; i++){
        if(arr[i] == key){
            return i;
        }
    }
    return -1;
}

그리고 보초법이라는 방법도 있는데 이 방법은 종료조건을 검사하지 않고 선형 검색을 하는 방법이다 

사용법을 인덱스의 마지막에 key값을 넣어주고 배열을 검사했을때 key값이 마지막 인덱스에 있으면 
데이터가 존재 하지 않는것이고 그전에 찾으면 배열에 데이터가 존재하는 것이라고 할 수 있다.

보초법

int linear_search_Sentinal_Method(int arr[], int n, int key){ // Sentinal_Method
    arr[n] = key; // 이 방법을 사용하기 위해서는 원소의 개수보다 배열이 더 커야함 
    int i = 0;
    for(i; i <= n ; i++){
        if(arr[i] == key) break;
    }
    return i == n ? -1 : i;
}

전체 코드

#include <bits/stdc++.h>
using namespace std;

int linear_search_while(const int arr[], int n , int key){ // while syntax
    int i = 0;
    while(true){
        if(i == n){
            return -1;
        }
        if(arr[i] == key){
            cout << i << '\n';
            return i;
        }
        i++;
    }
}

int linear_search_for(const int arr[], int n, int key){ // for syntax
    for(int i = 0; i < n; i++){
        if(arr[i] == key){
            return i;
        }
    }
    return -1;
}

int linear_search_Sentinal_Method(int arr[], int n, int key){ // Sentinal_Method
    arr[n] = key; // 이 방법을 사용하기 위해서는 원소의 개수보다 배열이 더 커야함 
    int i = 0;
    for(i; i <= n ; i++){
        if(arr[i] == key) break;
    }
    return i == n ? -1 : i;
}

int main(){
    int arr[] = { 30, 20, 10, 4, 5, 3, 2, 32, 540, 329, 900, 54, 239, 0 }; // 13
    cout << "Run start." << endl;
    if(int key = linear_search_for(arr,13,2) > -1 ? linear_search_for(arr,13,2) : 0){
        cout << "Linear Search success key index is = " << key << endl;
    }
    else{
        cout << "Do not found key index" << endl;
    }
    if(int key = linear_search_Sentinal_Method(arr, 13, 999) > -1 ? linear_search_Sentinal_Method(arr, 13, 999) : 0){
        cout << "Sentinal Method success key index is = " << key << endl;
    }
    else{
        cout << "Do not found key index" << endl;
    }
    return 0;
}

시간복잡도는 O(n)이다

참고로 인덱스를 0번으로 시작하니 찾지 못했을때의 반환값은 -1로 해주었다.

그리고 VSCode에서 한글이 깨져서 출력은 영어로 작성했는데 내 영어 실력이 짧아서 맞는 문법인지는 모르겟다.