1. 순차탐색 (Linear Search)
정의
순차탐색은 데이터를 리스트의 처음부터 끝까지 하나씩 비교하면서 찾고자 하는 값을 탐색하는 방식임. 이 방식은 정렬 안 된 리스트도 사용이 가능하다는 장점이 있어요.
동작 원리
- 리스트의 첫 번째 요소부터 시작해서 탐색할 값을 하나씩 비교하고
- 찾고자 하는 값이 발견되면 탐색을 종료하고 그 위치(인덱스)를 반환함
- 근데 리스트의 끝까지 탐색했는데 찾지 못했다면 값이 없다고 판단해요.
시간 복잡도
- O(n)
장점
- 데이터가 정렬 안 돼있어도 사용할 수 있어여.
- 구현이 간단하고 직관적이라 이해가 쉬워요.
단점
- 리스트의 크기가 커질수록 비효율적이에요.
- 평균적으로 모든 데이터를 비교해야 해서 성능이 좋지 않아요.
2. 이진탐색 (Binary Search)
정의
이진탐색은 정렬된 리스트에서 사용할 수 있는 탐색 알고리즘이에여. 리스트를 절반씩 나누어 탐색 범위를 좁혀가면서 원하는 값을 찾는 방식이라, 순차탐색보다 훨씬 빠르게 값을 찾을 수 있음요.
동작 원리
- 리스트의 중간 값을 선택하고.
- 중간 값이 찾고자 하는 값보다 크면 왼쪽 절반을, 작으면 오른쪽 절반을 탐색합니다.
- 이런식으로 과정을 반복해서 탐색 범위를 점점 좁혀가면서 값을 찾아요.
시간 복잡도
- O(log n)
장점
- 탐색 속도가 상당히 빨라여.
- 리스트의 크기가 커질수록 성능 차이가 극대화.
단점
- 리스트가 정렬되어 있어야 사용이 가능해서, 정렬 안 하면 피곤해여.
순차 탐색 vs 이진 탐색에 대해 알아봤슴다. 문제에 맞게 적절한거 알아서 선택해서 잘 써봅시다. 글 읽어주셔서 감사합니다.
