1. 순차 탐색(접근) 방법 [ 선형 탐색, 직렬 탐색 ]
- 탐색할 데이터가 모인 집합이 있으면 집합의 처음부터 끝까지 집합의 원소들을 비교하
여 원하는 데이터를 찾는 방법
- 데이터를 조작하지 않아 쉽게 구현할 수 있지만 비효율적인 탐색 방법 [단방향 탐색 ]
- 알고리즘이 단순하여 구현하기 쉽고 정렬되어 있지 않은 데이터의 집합에서
평균적으로 ( n + 1 ) / 2 번의 비교를 거치고, 최악의 경우 n 번 거친다.
- 시간 복잡도 : O(n)
- 알고리즘
l 입력 : Sequence 와 목표 값 x
l 출력 : 인덱스 값 i
l 후조건 : a[i]=x 또는 모든 a[i]≠ x 일때 I = -n
1. 0에서 n-1의 각 I 에 대해, 단계 2를 수행
2. a[i]=x 이면, i를 리턴
3. -n 을 리턴
1. 이진 탐색 [ binary Search algorithm ]
- 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘
- 주어진 시퀀스를 반복적으로 반으로 나누면서, 각 단계에서 그 목표를 포함하는 반쪽 범위에 탐색
- 시간 복잡도 : O(log n)
l 배열의 크기 : n, k번의 연산
l 한 번 연산 시 n개의 숫자가 반으로 줄어 1/2n이됩니다.
l 두 번 연산 시엔 1/4n 이 됩니다.
l k번째는 (1/2)^k n = 1
l n으로 양변을 나눈뒤, log를 씌어주면 지금의 시간 복잡도로 표시
- 알고리즘
l 입력 : 시퀀스와 목표 값 x
l 출력 : 인덱스 값 i
l 선 조건 : 시퀀스는 정렬되어 있음
l 후 조건 : ai =x; 또는 모든 j<p에 대해 aj<x이고 모든 j>p에 aj>x일때, i=-p-1
1. P=0. q=n-1
2. P<q 이면 단계 2-5를 반복
3. i = (p+q)/2 로 놓음
4. ai=x 이면, i를 리턴
5. ai<x 이면, p=i+1로 놓음, 그렇지 않다면 q=i-1로 놓음
6. -p-1 을 리턴
