2. 배열/리스트를 순회하면서 ‘하나씩 값을 비교’합니다. 3. 원하는 값을 찾는 경우 순회를 멈추고 값을 반환합니다.
[ 더 알아보기 ] 💡 선형 탐색과 이진 탐색의 차이점
- 일반적으로 특정 값을 탐색하고자 할 때 값을 찾는 방법은 ‘이진 탐색’을 이용하는 것이 ‘선형 탐색’보다 더 빠릅니다.
- 이진 탐색은 정렬된 배열에서 원하는 값을 찾는 알고리즘이며, 중간값을 찾아 탐색 범위를 반으로 줄이면서 값을 찾아갑니다. - 이에 비해 선형탐색은 배열 전체를 순회하면서 값을 찾기 때문에 배열의 크기와 상관없이 속도가 일정하게 증가합니다.
💡 선형 탐색과 순차적 탐색의 차이점
- 선형 탐색과 순차적 탐색은 동일한 의미로 사용됩니다. - 선형 탐색의 경우 찾고자 하는 값이 나오지 않으면 종료가 되지만 순차적 탐색의 경우는 반복을 멈추지 않고 값이 나올 때까지 반복합니다.
[참고] 선형 탐색 vs 이진 탐색 차이점 요약
분류
선형 탐색(Linear Search)
이진 탐색(Binary Search)
정렬여부
정렬되지 않은 배열/리스트
정렬된 배열/리스트
탐색속도
느림
빠름
탐색범위
처음부터 끝까지
중간값을 기준으로 좌/우측 반 중 하나
구현방식
for/while 루프 사용
재귀 함수 사용
시간 복잡도
O(n)
O(log n)
2. 선형 탐색의 사용처
💡 데이터의 크기가 작거나 정렬되어 있지 않은 경우에 주로 사용이 됩니다.
💡 예를 들어, 10개 이하의 원소로 이루어진 리스트에서 값을 찾을 때는 선형 탐색이 효율적입니다.
💡 하지만 데이터의 크기가 커지면 검색 속도가 급격히 느려지므로, 큰 데이터셋에서는 다른 탐색 알고리즘을 사용하는 것이 좋습니다.
3. 선형 탐색의 성능
💡 선형 탐색의 경우 시간 복잡도의 ‘빅오 표기법’을 이용하여 확인하였을때 선형 시간인 O(n)으로써 이진 탐색보다는 느리지만 상대적으로 빠른 속도를 가지고 있습니다.
표기법
이름
시간 복잡도
설명
예시
O(1)
상수
상수 시간
입력 크기와 상관없이 일정한 실행 시간을 가집니다.
배열에서 원소 하나 찾기
O(logn)
로그
로그 시간
입력 크기가 증가함에 따라 실행 시간이 로그함수의 형태로 증가합니다.
이진 탐색 알고리즘
O(n)
선형
선형 시간
입력 크기와 비례하는 실행 시간을 가집니다.
선형 탐색 알고리즘
O(nlogn)
로그 선형
선형 로그 시간
입력 크기가 증가함에 따라 실행 시간이 로그함수와 선형 함수의 곱의 형태로 증가합니다.
병합 정렬, 힙 정렬 알고리즘
O(n^2)
이차
이차 시간
입력 크기의 제곱에 비례하는 실행 시간을 가집니다.
선택 정렬, 버블 정렬, 퀵 정렬 알고리즘
O(2^n)
지수
지수 시간
입력 크기의 지수에 비례하는 실행 시간을 가집니다.
부분집합
O(n!)
계승
팩토리얼 시간
입력 크기의 팩토리얼에 비례하는 실행 시간을 가집니다.
외판원 문제
💡 [참고] 선형 탐색의 경우 이진 탐색을 제외한다면 다른 탐색들과 비교해봐도 속도가 빠름을 확인할 수 있습니다.
알고리즘 명
최악 시간 복잡도
선형 탐색
O(n)
이진 탐색
O(log n)
보간 탐색
O(log(log n))
해시 탐색
O(1)
깊이 우선 탐색
O(V + E)
4. 선형 탐색의 예시
4.1. 배열 내의 숫자 찾는 예시
💡 해당 코드는 선형탐색의 예시를 보여주고 있습니다.
💡 예시는 파라미터로 배열 ‘arr’와 값 ‘x’를 받았을때, 배열을 순회하면서 요소 중 ‘x’에 해당하는 값을 찾았을 경우 반환하며, 찾지 못한 경우는 -1을 반환하는 함수입니다.
public static int linearSearch(int[] arr, int x) {
int n = arr.length;
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
4.2. 배열 내의 문자열 찾는 예시
💡 해당 코드는 선형탐색의 예시를 보여주고 있습니다. 💡 예시는 파라미터로 배열 ‘arr’와 값 ‘target’을 받았을 때, 배열을 순회하면서 요소 중 ‘x’에 해당하는 값을 찾았을 경우 반환하며, 찾지 못한 경우는 -1을 반환하는 함수입니다.
public static int linearSearch(String[] arr, String target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i].equals(target)) {
return i;
}
}
return -1;
}
💡 [참고] 좀 더 다양한 알고리즘에 대해 알고 싶으시면 아래의 글을 참고하시면 도움이 됩니다.
