개념
이진 탐색이란 정렬되어있는 데이터 집합을 이분화하여 탐색하는 방법이다. 이때 정렬된 데이터가 키 포인트인데 정렬이 되어있지 않다면 쓸 수 없다. start, end, mid를 이용하여 target을 탐색을 하는데 여기서 mid는 (start + end) // 2 한 값 즉 중간값이다. 이제 3가지 경우가 존재하는데 각각의 경우는 다음과 같다.
1. array[mid] == target
2. array[mid] > target
3. array[mid] < target
1번의 경우 단순하게 해당 mid값을 return 해주면 된다.
2번의 경우 중간값에 해당하는 값이 찾고자 하는 값 보다 크기 때문에 중간값 좌측의 구간만 다시 탐색을 해주면 된다. 따라서 end = mid - 1
3번의 경우 중간값에 해당하는 값이 찾고자 하는 값 보다 작기 때문에 중간값 우측의 구간만 다시 탐색을 해주면 된다.
따라서 start = mid + 1
구현은 재귀의 경우가 반복문의 경우보다 느리다고 알고 있기 때문에 더 효율적인 반복문의 형태로 구현을 한다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
if array[mid] == target:
return mid
elif array[mid] > target:
end = mid - 1
else:
start = mid + 1
return -1 # target을 array에서 찾지 못한 경우
n, x = map(int, input().split())
data = list(map(int, input().split()))
result = binary_search(data, x, 0, n-1)
if result == -1:
print("찾으시는 숫자가 존재하지 않습니다")
else:
print(result + 1)
|
cs |
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
| 에라토스테네스의 체를 이용한 소수 판별 (Python) (0) | 2020.12.21 |
|---|---|
| 가장 긴 증가하는 부분 수열 - Longest Increasing Subsequence (Python) (0) | 2020.12.19 |
| bisect 라이브러리를 이용한 손쉬운 이진탐색 (Python) (0) | 2020.12.15 |
| BFS 너비 우선탐색 (Python) (0) | 2020.12.03 |
| DFS 깊이 우선탐색 (Python) (0) | 2020.11.30 |
