순차탐색 (Sequential Search)
순차탐색이란?
리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다.
순차탐색코드
def sequentail_search(n,target,array):
#각 원소를 하나씩 확인하며
for i in range(n):
#현재의 원소가 찾고자 하는 원소가 동일한 경우
if array[i] == target:
return i+1 #현재의 위치 변환(인덱스는 0부터 시작하므로 1더하기)
#생성할 원소 개수와 타겟값입력
input_data = input().split()
n = int(input_data[0]) #원소의 개수
target = input_data[1] #찾고자 하는 문자열
#배열 입력받기
array = input().split()
#순차 탐색 수형결과 출력
print(sequentail_search(n,target,array))시간복잡도
데이터를 하나하나 확인하므로
최악의 경우 시간복잡도는 O(N) 이 된다.
이진탐색
이진탐색이란?
이진 탐색(Binary Search)은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
이진 탐색은 탐색 범위를 반으로 좁혀가며 데이터를 탐색한다.
이진 탐색을 하기 위해선 3가지 변수를 선언해야한다.
-> 시작점, 끝점, 중간점
찾으려는 데이터와 중간점(Middle) 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾는 것이 이진 탐색 과정이다.
예시
이미 정렬된 10개의 데이터중 4라는 값의 원소를 찾아보자.
Step1
0부터 18까지의 원소가 오름차순으로 정렬되어있다.
0이 시작점( [0] ), 8이 중간점( [4] ), 18이 끝점( [9] )이 된다.
여기서 중간점은 {(시작점의 번지값)+(끝점의 번지값)}//2 으로 구한다.
중간점은 8이므로 찾는 원소인 4보다 값이 크다.
중간점보다 큰값들이 위치한 4~10번지는 탐색할 필요가 없게 된다.
그러므로 끝점을 [4] 에서 [3] 으로 옮겨준다.
Step 2
끝점이 3번지로 이동함으로 써 끝점의 값이 6이 되었고, 중간점은 1번지가 되어 중간점의 값은 2가 되었다.
찾으려는 원소 4는 중간점의 값 2보다 더 크므로 2이하의 값, 즉 0~1번지의 값은 탐색이 필요없어지게 된다.
그러므로 시작점을 2번지로 변경해준다.
Step3
중간점이 타겟값과 일치하므로 탐색을 종료한다.
전체 데이터는 총 10개지만, 총 3번의 탐색과정으로 원하는 값을 찾을 수 있다.
시간복잡도
이진 탐색은 한 번 탐색할 때마다 탐색해야 할 원소의 개수가 절반씩 줄어든다는 장점이 있다.
그래서 시간 복잡도가 O(logN) 이다.
