선형 검색(Linear Search)
배열에서 검색하는 방법 중 가장 기본적인 알고리즘입니다.
직선(선형)으로 늘어진 배열에서 검색하는 경우 원하는 원소를 찾을 때까지 맨 앞에서부터 순서대로 검색하는 알고리즘입니다.
2 | 4 | 1 | 6 | 7 | 3 | 5 |
가령 위와 같은 배열이 있다고 가정해봅시다. 우리는 원소 3을 찾고 싶습니다.
그렇다면 맨 앞 배열의 0번자리부터 스캔을 시작하고, 6번째 스캔에서 3을 찾아내게 됩니다.
원하는 3을 찾았으니 검색은 성공하고 알고리즘은 종료되겠죠.
그러나 8을 찾는다고 가정해보겠습니다.
앞에서부터 스캔을 하다가 6번자리까지 지나도 보이지 않으니 배열의 맨 끝 원소를 지나가게 되고, 알고리즘은 검색이 실패한 채 종료됩니다.
위의 설명과 같이 선형 검색이 종료되는 조건은 2가지가 있습니다.
1. 검색에 실패하거나(검색할 값을 찾지 못한 채 배열의 끝까지 검색한 경우)
2. 검색에 성공하거나(검색할 값과 같은 원소를 찾은 경우)
이처럼 선형 검색은 원소의 값이 정렬되지 않은 배열에서 검색할 때 사용하는 유일한 방법입니다.
그러나 선형 검색은 검색을 반복할 때마다 종료 조건 2가지를 판단하게 됩니다. 이는 배열이 커지면 커질수록 비효율적으로 변하게 되죠.
그런데 위 종료되는 조건 판단 횟수를 절반으로 줄일 수 있는 방법이 있습니다.
바로 보초법입니다. 선형검색에 기능을 업데이트 했다고 생각하시면 됩니다.
배열의 맨 끝에 찾고자 하는 원소 값을 추가하면 됩니다. 이를 보초라고 합니다.
2 | 4 | 1 | 6 | 7 | 3 | 5 | 8 |
기존의 배열의 맨 끝에 8을 추가했습니다. 이렇게 되면 조건 1번은 만족하지 않으니 어떻게든 2번만 만족하면 되겠죠.
'알고리즘, 자료구조' 카테고리의 다른 글
[알고리즘] 누적 합 (Prefix Sum) (0) | 2025.02.21 |
---|---|
[알고리즘] 깊이 우선 탐색 (Depth-First Search, DFS) (0) | 2025.01.05 |
[알고리즘] 벨만-포드 알고리즘 (Bellman-Ford Algorithm) (0) | 2025.01.04 |
컴퓨팅적 사고 (0) | 2022.03.21 |
알고리즘(Algorithm) (0) | 2022.03.20 |