선형 검색 알고리즘 소개: 소개 및 기능[예제 포함]

검색이란 무엇입니까?

검색은 요소 목록에서 주어진 요소를 찾는 프로세스입니다. 특정 레코드를 검색하는 데 도움이 됩니다. 따라서 주어진 항목의 위치를 ​​식별하는 기술입니다. 검색 프로세스의 성공 여부는 검색할 항목이 식별되었는지 여부에 따라 다릅니다.

데이터 구조는 두 가지 방법을 통해 데이터를 검색할 수 있습니다.

1. 선형 검색 또는 순차 검색
2. 이진 검색

선형 검색

선형 검색 알고리즘은 데이터의 순차 검색을 위한 알고리즘 유형입니다. 이 알고리즘은 O(n) 복잡도를 가진 주어진 요소를 찾습니다. 아이템 컬렉션에 적용됩니다. 데이터의 모든 항목을 순차적으로 검색하여 검색된 요소와 일치하면 반환합니다. 일치하는 항목이 없으면 수집된 데이터가 끝날 때까지 검색이 계속됩니다. 기본적으로 목록을 순회하면서 모든 요소를 ​​탐색하는 기술입니다. 검색 알고리즘은 정렬된 데이터와 정렬되지 않은 데이터 모두에 적용할 수 있습니다. 이진 검색 알고리즘 및 해시 테이블과 같은 다른 검색 알고리즘에서 제공하는 더 빠른 검색 옵션으로 인해 실질적으로 선형 검색은 거의 사용되지 않습니다.

선형 탐색 알고리즘의 단계

• 사용자가 검색 요소를 읽습니다.
• 검색할 요소는 목록의 첫 번째 요소로 압축됩니다.
• 요소가 일치하면 반환이 생성됩니다.
• 요소가 일치하지 않으면 검색할 요소가 목록의 두 번째 요소와 비교됩니다.
• 요소가 일치할 때까지 프로세스가 반복됩니다.

선형 탐색 알고리즘의 특징

1. 일반적으로 정렬되지 않거나 정렬되지 않은 데이터의 작은 목록에 적용됩니다.
2. 시간은 요소 수에 선형적으로 의존하므로 O(n)인 경우 시간 복잡도를 갖습니다.
3. 구현은 매우 간단합니다.

선형 검색 알고리즘

항목이 발견되지 않는 한 계속 반복되는 방법이 계속됩니다.

• algorithm Seqnl_Search(목록, 항목)
• 사전: 목록 != ;
• Post: 찾은 경우 항목의 인덱스를 반환하고, 그렇지 않은 경우: 1
• 인덱스 <- fi
• while index < list.Cnt and list[index] != item //cnt: 카운터 변수
• 인덱스 <- 인덱스 + 1
• 동안 종료
• index < list.Cnt 및 list[index] = 항목인 경우
• 반환 인덱스
• 종료
• 반환: 1
• 끝 시퀀스_검색

선형 검색의 예

문제: n개의 요소로 구성된 배열 arr[]이 주어지면 arr[]에서 주어진 요소 x를 검색하는 함수를 작성하십시오.

그림 1: 선형 검색 알고리즘의 구현을 보여주는 코드의 예

원천

선형 검색 알고리즘은 여러 프로그래밍 언어에서 사용할 수 있습니다.

1. Python의 선형 검색

그림 2: Python 언어의 선형 검색 알고리즘을 보여주는 코드의 예

원천

출력: 요소가 인덱스 3에 있습니다 .

2. C에서 선형 검색

그림 3: C 언어의 선형 검색 알고리즘을 보여주는 코드의 예

원천

출력 : 요소가 인덱스 3에 있음

3. 데이터 구조의 선형 검색

데이터 구조의 선형 탐색 문제에 대한 의사 코드는 다음과 같습니다.

그림 4: 선형 검색 알고리즘을 위한 의사 코드

원천

이진 검색

이진 검색은 요소 배열에서 요소를 검색하는 알고리즘입니다. 선형 탐색 알고리즘과 비교하여 이진 탐색 알고리즘은 정렬된 데이터 목록에 적용됩니다.

이진 검색 알고리즘에는 다음 단계가 포함됩니다.

• 목록 또는 배열의 중간에 있는 요소와 검색할 요소를 비교합니다.
• 요소가 목록의 요소와 일치하면 중간 요소의 인덱스를 반환합니다.
• 일치하는 항목이 반환되지 않으면 요소가 중간에 있는 요소보다 크거나 작은지 확인합니다.
• 중간 요소보다 값이 큰 요소의 경우 배열의 오른쪽에서 검색이 수행됩니다.
• 유사하게, 요소가 중간 요소보다 값이 작으면 검색이 목록의 왼쪽으로 계속됩니다.

따라서 데이터에 정렬된 방식으로 많은 수의 막대 요소가 포함된 경우 이진 검색이 가장 잘 적용됩니다. 이것은 목록/배열이 정렬되어야 하는 검색 알고리즘에 대한 필수 요소가 됩니다.

이진 검색의 기능

• 이진 검색 알고리즘은 배열에서 많은 수의 요소를 검색하는 데 유용합니다.
• 이진 탐색 알고리즘의 시간 복잡도는 O(logn)입니다.
• 이진 검색 알고리즘의 구현은 간단합니다.

이진 검색 알고리즘

• 알고리즘 Binary_Search(목록, 항목)
• L을 0으로 설정하고 R을 n으로 설정: 1
• L > R이면 Binary_Search가 실패로 종료됩니다.
• 또 다른
• m(중간 요소의 위치)을 (L + R) / 2의 바닥으로 설정합니다.
• Am < T이면 L을 m + 1로 설정하고 3단계로 이동합니다.
• Am > T인 경우 R을 m:1로 설정하고 3단계로 이동합니다.
• 이제 Am = T,
• 검색이 완료되었습니다. 반환(m)

결론

이 글에서는 선형 탐색 알고리즘이 무엇인지 살펴보고 선형 탐색 알고리즘을 사용하여 목록에서 특정 요소를 검색하는 방법에 대해서도 자세히 공부했습니다. 마지막으로 Python 3을 언어로 사용하여 선형 검색 알고리즘을 실제로 구현하고 원하는 결과를 얻는 방법도 보았습니다.

데이터 과학에 관심이 있다면 IIIT-B 및 upGrad의 데이터 과학 이그 제 큐 티브 PG 프로그램을 확인해야 합니다. 훨씬 더.