알고리즘 요약
이진탐색 (binary search)
- 정렬된 배열내에서 값의 크기에 맞는 쪽으로만 찾는 과정을 반복한다.
- 중간요소 값보다 작으면 좌측에서 계속 찾고, 크면 우측에서 계속 찾는다.
- 배열이 정렬되어 있는 경우 효과적
- 시간복잡도: O(log n)
탐색과정 설명
① ② ③ ④ ⑤ : 위치번호
[1, 2, 3, 4, 6] :숫자열이 있을 경우, 4를 찾는다 가정하면.
-좌측 비교 시작값을 ①, 우측 끝값을 ⑤로 두고, 중앙값 ③3과 비교.
[1, 2, 3, 4, 6]
-찾는 값 3보다 커야 하므로 시작위치를 ③+1로 두고 우측에서 찾는다.
[1, 2, 3, 4, 6]
-④와 ⑤의 중앙값 ④4 와 비교. 찾았기 때문에 탐색완료
# 재귀함수로 구현
def bin_search_r(a, v, low, high):
if low > high: # 원하는 값이 없는 상태면 None 리턴해서 끝냄
return None
mid = (low + high) // 2 # 중간위치를 찾음
if v == a[mid]: # 중간 위치 값과 찾는 값이 같으면 위치 리턴해서 끝냄
return mid
elif v < a[mid]: # 중간값보다 작으면 더 작은 위치에서 반복(재귀)
return bin_search_r(a, v, low, mid - 1)
else: # 중간값보다 크면 더 큰 위치에서 반복(재귀)
return bin_search_r(a, v, mid + 1, high)
# 반복문으로 구현
def bin_search(a, v):
low, high = 0, len(a) # 좌측 위치값과 우측 위치값 초기화
while low < high: #좌측 위치값이 우측 위치값보다 작으면 계속 루프
mid = (low + high) // 2 # 중간 위치 계산
if v == a[mid]: # 찾는 값과 같으면 리턴 끝.
return mid
elif v < a[mid]: #찾는 값이 중간값 보다 작으면 위치를 더 좌측으로 설정
high = mid
else: # 찾는 값이 중간값 보다 크면 위치를 더 우측으로 설정
low = mid + 1
return None #찾는 값이 없으면 None 리턴
a = [1, 2, 3, 4, 6]
print(bin_search_r(a, 4, 0, len(a))) # 결과는 3
print(bin_search(a, 4)) # 결과는 3
#include <stdio.h>
// 데이터가 있는 배열을 받아서 key 값이 존재하는 지 확인하는 함수
// 값이 있으면 인덱스값, 없으면 -1 리턴
int bin_search(int a[], int len, int key) { // a:데이터 배열, len:배열길이, key:찾을 값
int low = 0, high, mid;
high = len -1;
while (low < high) { // 찾을 데이타가 있는 동안 루프
mid = (low + high) / 2; // 중간 인덱스값 계산
if (key == a[mid]) return mid; // key값과 같으면 인덱스 리턴 끝.
else if (key < a[mid]) high = mid - 1; // 비교값이 크면 탐색범위를 아래로
else low = mid + 1; // 비교값이 작으면 탐색범위를 위쪽으로
}
return -1; // 루프에서 찾지 못하면 찾는 값이 없으므로 -1 리턴
}
// 함수 테스트
int main() {
int a[] = {6, 2, 3, 4, 1}, len = sizeof(a) / sizeof(a[0]);
printf("%d", bin_search(a, len, 3)); //결과: 2
return 0;
}