선형 검색: Python, C++ 예시

검색 알고리즘이란 무엇인가요?

검색 알고리즘은 주어진 데이터 구조를 가진 요소 또는 객체들의 모음에서 특정 요소 또는 객체를 찾는 알고리즘입니다. 예를 들어, 주어진 높이 목록에서 최소 높이를 찾거나, 숫자 목록 또는 배열에서 최고 점수를 찾는 알고리즘이 있습니다. 대표적인 검색 알고리즘으로는 선형 검색, 이진 검색, 점프 검색, 피보나치 검색 등이 있습니다.

선형 검색이란 무엇입니까?

선형 검색 선형 검색은 가장 간단한 검색 알고리즘 중 하나입니다. 주어진 리스트나 배열에서 원하는 요소를 하나씩 찾아냅니다. 선형 검색은 리스트 전체를 순회하며 특정 요소가 찾고자 하는 요소와 같은지 확인합니다. 이 알고리즘은 또한 가장 간단한 검색 알고리즘이라고도 불립니다. 순차 검색.

선형 검색 기능은 무엇을 합니까?

정수 배열은 "Numbers,” 변수 “item”에는 검색할 정수가 포함됩니다.

이제 선형 검색 알고리즘은 다음과 같은 출력을 제공할 수 있습니다.

• "-1"은 주어진 요소가 배열에서 발견되지 않았음을 의미합니다.
• 0에서 n-1 사이의 숫자; 이는 검색 요소를 찾았으며 배열에 있는 요소의 인덱스를 반환한다는 의미입니다. 여기서 n은 배열의 크기를 나타냅니다.

선형 검색은 어떻게 작동하나요?

정수들이 담긴 배열이 있다고 가정해 봅시다. 주어진 숫자를 배열에서 찾는 것이 목표입니다.

• 숫자가 배열에 있으면 해당 숫자의 인덱스를 반환해야 합니다.
• 주어진 숫자를 찾을 수 없으면 -1을 반환합니다.

순서도에서 “Data”는 정수 배열이고, “N”은 배열의 크기, “item”은 배열에서 검색하려는 숫자입니다.

선형 검색 알고리즘의 흐름도:

순서도의 단계는 다음과 같습니다.

단계 1) 검색항목 'item'을 읽어보세요.

단계 2) i=0, 인덱스=-1로 초기화합니다.

단계 3) 만약 내가

단계 4) Data[i]가 "item"과 같으면 5단계로 이동합니다. 그렇지 않으면 6단계로 이동합니다.

단계 5) 인덱스 = i (해당 항목이 인덱스 번호 i에서 발견되었으므로). 8단계로 이동합니다.

단계 6) 나는 = 나는 +1이다.

단계 7) 3 단계로 이동합니다.

단계 8) 중지합니다.

단순화를 위해 정수 배열의 예를 제공합니다. 선형 검색은 문자열, 객체 배열 또는 구조체에도 적용 가능합니다.

별명 Code 순차 탐색 알고리즘의 경우

다음 의사 코드는 위에서 설명한 선형 검색의 논리를 나타냅니다. 배열의 첫 번째 인덱스부터 순회하며 일치하는 항목이 있으면 해당 위치를 반환하고, 그렇지 않으면 -1을 반환합니다.

function linearSearch: in → Data[], item
    foundAt = -1
    for i in (0 to data.length):
        if data[i] equals item:
            // item is found in the array
            // returning the index
            return i
    // item not found in the array
    // -1 means no item found, as a negative index is not valid
    return -1

C++ Code 선형 검색 예

다음은 전체 내용입니다. C++ 순차 검색을 구현하고 검색된 값의 인덱스를 출력하는 프로그램입니다.

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

int linearSearch(int *arr, int item, int n) {
    int idx = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] == item) {
            idx = i;
            break;
        }
    }
    return idx;
}

int main() {
    int array[] = {1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10};
    int n = sizeof(array) / sizeof(array[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(array, item, n);
    if (idx >= 0) {
        cout << item << " is found at index " << idx << endl;
    } else {
        cout << "Could not find " << item << " in the array" << endl;
    }
}

출력:

Enter a number to search: -10
-10 is found at index 14

Python Code 선형 검색 예

동일한 논리가 적용됩니다. Python 리스트 인덱스를 순회하는 단일 루프를 사용하여 일치하는 요소의 위치를 ​​반환합니다.

def linearSearch(data, item):
    for i in range(len(data)):
        if data[i] == item:
            return i
    return -1

data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10]
item = int(input("Enter a number to search: "))
idx = linearSearch(data, item)
if idx >= 0:
    print("{} is found at index {}".format(item, idx))
else:
    print("{} was not found".format(item))

출력:

Enter a number to search: -10
-10 is found at index 14

선형 탐색 알고리즘의 복잡도 분석

일반적으로 시간 복잡도는 특정 작업을 수행하는 데 필요한 CPU 시간을 의미합니다. 선형 검색 알고리즘에서 작업은 배열의 요소 중에서 검색 키를 찾는 것입니다.

시간 복잡도에는 세 가지 유형이 있습니다.

• 최악의 시나리오
• 최고의 사례 시나리오
• 평균 사례 시나리오

최악의 시나리오에서 선형 검색의 시간 복잡도:

크기가 "n"인 배열에서 선형 검색을 수행해야 한다고 가정해 보겠습니다. 검색 대상은 인덱스 0부터 n-1 사이에서 찾을 수 있습니다. 최악의 경우, 알고리즘은 배열의 모든 요소를 ​​검색 대상 요소와 일치시키려고 시도할 것입니다.

이 경우 최악의 경우 시간 복잡도는 O(n)이 됩니다. 여기서 "O"(빅 O 표기법)는 시간 복잡도 함수를 의미합니다.

최고의 시나리오에서 선형 검색의 시간 복잡도:

배열의 첫 번째 위치에 있는 요소를 찾는다고 가정해 보겠습니다. 이 경우 선형 검색 알고리즘은 배열의 모든 n개 요소를 검색하지 않습니다. 따라서 시간 복잡도는 O(1)이 됩니다. 즉, 상수 시간입니다.

평균적인 경우의 선형 검색의 시간 복잡도:

배열의 중간 인덱스에서 요소가 발견되면 선형 검색에 대한 평균 케이스 복잡도는 O(N)이라고 할 수 있습니다. 여기서 N은 배열의 길이를 의미합니다.

선형 탐색 알고리즘의 공간 복잡도:

선형 검색의 공간 복잡도는 항상 O(N)입니다. 왜냐하면 선형 검색 함수에서는 어떤 종류의 임시 변수도 저장하거나 사용할 필요가 없기 때문입니다.

선형 검색 알고리즘을 개선하는 방법

프로그램 실행 주기 동안 검색은 여러 번 수행될 수 있습니다. 또한 선형 검색 알고리즘을 실행하여 특정 키를 여러 번 검색하는 것도 가능합니다. "를 사용할 수 있습니다.이진 검색 알고리즘” 배열이 정렬된 배열인 경우.

배열이 10개의 숫자로 구성되어 있고 대상 요소가 5000번째 인덱스에서 발견된다고 가정합니다. 따라서 알고리즘은 5000개의 요소를 비교하려고 합니다. 이제 비교는 CPU에 많은 부담을 주는 작업입니다. 선형 검색 알고리즘을 최적화하기 위해 두 가지 옵션이 있습니다.

• 전치
• 앞으로 이동

전치:

이 방법에서는 배열에서 찾고자 하는 요소를 바로 앞 요소와 교환합니다. 예를 들어 다음과 같은 배열이 있다고 가정해 보겠습니다.

데이터[] = {1,5,9,8,7,3,4,11}

이제 검색을 하려고 합니다. 4. Steps of Transposition:

단계 1) "4"는 인덱스 6에 있습니다. XNUMX번의 비교가 필요했습니다.

단계 2) 데이터[6]와 데이터[5]를 교환합니다. 그러면 데이터 배열은 다음과 같습니다.

데이터[] = {1,5,9,8,7,4,3,11}

단계 3) 4를 다시 검색하세요. 인덱스 5에서 찾았습니다. 이번에는 XNUMX번의 비교가 필요했습니다.

단계 4) data[5]와 data[4]를 바꿉니다. 그러면 data 배열은 다음과 같이 됩니다.

데이터[] = {1,5,9,8,4,7,3,11}

자, 보시면 아시겠지만, 키를 검색하는 빈도가 높을수록 인덱스 값이 감소합니다. 즉, 비교 횟수가 줄어드는 것입니다.

앞으로 이동:

이 방법에서는 검색 요소를 0번째 인덱스로 바꿉니다. 다시 검색하면 O(1) 시간 안에 찾을 수 있기 때문입니다.

선형 검색 알고리즘 적용

다음은 우리가 사용할 수 있는 몇 가지 선형 검색 애플리케이션입니다.

• 배열 크기가 작거나 목록에 요소가 몇 개 없는 경우에는 선형 검색을 사용하는 것이 더 쉽습니다.
• 선형 검색 방법은 단일 또는 다차원 배열 또는 다른 데이터 구조.
• 일반적으로 선형 검색은 "순서가 지정되지 않은" 데이터에서 검색을 수행하는 데 간단하고 효율적입니다. 주어진 정렬되지 않은 목록에서 단일 데이터를 쉽게 가져올 수 있습니다.

자주 묻는 질문