들어가며
본 포스팅에서는 순차 탐색(Sequential Search)과 이진 탐색(Binary Search)에 대해 소개합니다.
📌 순차 탐색이란?
순차 탐색(Sequential Search)이란, 특정 데이터를 찾기 위해 앞에서부터 차례대로 값을 비교해나가는 탐색 방식입니다.
1️⃣ 가장 첫 번째 데이터를, 찾고자하는 데이터(타겟)과 비교합니다.
2️⃣ 값이 서로 일치하지 않는다면, 다음 데이터로 이동하여 비교합니다.
3️⃣ 이를 반복하며 일치할 때, 탐색을 종료합니다.
✅[ CODE ]
def sequential_search(n, target, arr):
for i in range(n):
if arr[i] == target:
return i + 1i + 1 번째의 데이터가 타겟과 동일하다는 결과를 얻을 수 있다.
☑️ 시간 복잡도
데이터의 정렬 여부와는 상관없이 앞에서부터 차례대로 비교해 나가야 합니다. 따라서, 원소의 개수 N개 만큼의 비교 연산이 필요해지므로, 순차 탐색의 최악의 시간 복잡도는 $O(N)$입니다.
📌 이진 탐색이란?
이진 탐색(Binary Search)이란, 특정 데이터를 찾기 위해 탐색 범위를 절반씩 좁혀나가면 탐색하는 방식입니다.
리스트 내의 데이터가 정렬되어 있어야만 사용할 수 있다는 특징이 있습니다.
1️⃣ 탐색 범위의 시작점과 끝점을 통해 중간점을 구합니다. (소수점 이하 무시)
2️⃣ 찾고자 하는 데이터와 중간점을 비교합니다.
3️⃣ 중간점 < 타겟 데이터이라면, 시작점을 중간점의 다음 칸으로 옮깁니다.
4️⃣ 중간점 > 타겟 데이터이라면, 끝점을 중간점의 이전 칸으로 옮깁니다.
5️⃣ 중간점과 타겟 데이터가 일치하면, 탐색을 종료합니다.
아래의 예시와 함께 보자면,
1. 중간점인 11과 타겟 데이터인 7을 비교하면, 중간점이 더 큽니다. 따라서, 끝점을 중간점의 이전 칸으로 옮겨줍니다.
2. 다시 측정한 중간점인 4와 타겟 데이터인 7을 비교하면, 이번엔 중간점이 더 작습니다. 따라서, 시작점을 중간점의 다음 칸으로 옮겨줍니다.
3. 다시 측정한 중간점인 7과 타겟 데이터인 7을 비교하면, 일치하므로 탐색을 종료합니다.
☑️ 시간 복잡도
데이터의 범위가 절반씩 좁혀지기 때문에 연산 횟수는 $log_2(N)$에 비례하므로 시간 복잡도는 $O(logN)$입니다.
탐색하고자 하는 데이터의 개수가 1000만개 이상이거나, 탐색 범위의 크기가 1000억 이상인 경우, 이진 탐색을 활용하면 좋습니다.
✅[ CODE ] - 재귀함수 이용
def binary_search(start, end, arr, target):
if start > end:
return None
# 시작점과 끝점으로 중간점을 구한다.
middle = (end + start) // 2
# 타겟과 일치한다면, 탐색 종료
if target == arr[middle]:
return middle + 1 # 인덱스 + 1 번째 수라는 의미
# 타겟과 비교하여, 시작점이나 끝점을 옮겨준다.
if target < arr[middle]:
end = middle - 1
elif target > arr[middle]:
start = middle + 1
return binary_search(start, end, arr, target)
n, target = map(int, input().split())
arr = list(map(int, input().split()))
result = binary_search(0, n - 1, arr, target)
print(result)재귀함수를 이용하여 반복적으로 범위를 좁혀나가며 구현된 방식입니다.
✅[ CODE ] - 반복문 이용
def binary_search(start, end, arr, target):
# 시작점이 끝점보다 작거나 같을 동안에 실행
while start <= end:
middle = (end + start) // 2
if target == arr[middle]:
return middle + 1
if target < arr[middle]:
end = middle - 1
else:
start = middle + 1
return None
n, target = map(int, input().split())
arr = list(map(int, input().split()))
result = binary_search(0, n - 1, arr, target)
print(result)반복문을 이용하여, 범위를 좁혀나가며 구현된 방식입니다.
포스팅 내용에 오류가 있는 경우, 댓글로 남겨주시면 감사드리겠습니다. 😃😃
힘내자아!
출처 ) 이것이 코딩 테스트다 with Python