[알고리즘] 이진탐색 / 이분탐색 (Binary Search) (Python)
보통 원하는 원소를 찾고자 할 때 처음부터 끝까지 탐색하는 선형 탐색을 주로 사용한다.
선형 탐색은 데이터의 크기가 너무 크지 않다면 딱히 고려할 조건이 없기 때문에 구현이 쉽기 때문이다.
하지만 데이터의 크기가 너무 커진다면 얘기가 달라진다.
그래서 나온 탐색 방법이 이진 탐색이다.(이분 탐색도 같은 말)
먼저 기본적인 개념은 순차적으로 정렬이 된 상태에서 특정 원소를 찾을 때까지 범위를 절반씩 줄이고 더 이상 찾을 범위가 없으면 해당 원소는 없다고 판단하는 알고리즘이다.
N개의 Data가 있을 때 범위를 절반씩 줄여나가므로 O(logn)의 아주 효율적인 시간 복잡도를 가지는데 여기서 중요한 점은 정렬된 상태여야 한다는 것이다.
왜냐하면 범위를 줄여나갈 때 찾고자 하는 원소와 현재 범위의 중간값을 비교해서 일치하면 중단, 일치하지 않으면 절반에 해당하는 범위엔 찾고자 하는 원소가 없다는 전제하에 범위를 줄여나가는 방식인데 정렬된 상태가 아니라면 이처럼 범위를 줄여나갈 수가 없다.
따라서 정렬된 Data를 탐색하거나 정렬하여 탐색할 수 있는 범위가 주어진다.
참고로 Python의 sort함수를 쓰면 O(nlogn)의 시간 복잡도를 가지므로 100만의 Input정도는 충분히 정렬 후 탐색할 수 있다.
그림의 예시를 따라가다 보면 쉽게 이해할 수 있을 것이다. (예시는 오름차순 리스트를 하며 내림차순은 반대로 하면 된다)
![data=[1,2,4,5,6,8,9]](https://blog.kakaocdn.net/dn/Dq4Jk/btrmK0xgMr0/KbsYQmG4kYb8n1a8m9Nsv0/img.jpg)
먼저 리스트의 전체 범위에서 시작해야 하므로 Left와 Right 두 개의 변수가 필요하다.
Left는 시작을 뜻하는 0(0번째 인덱스), Right는 끝을 뜻하는 len(data)-1로 선언하면 된다.
이제 아주 간단한 사전 준비는 끝났다.
Left와 Right의 위치가 역전된다면 더 이상 탐색할 범위가 없다는 뜻이므로 Left <= Right인 동안 반복을 계속 돌려주면 된다.
예시로 2와 7을 찾도록 해보겠다.
빨간색 화살표는 중앙값(변수명은 mid)을 뜻하고 찾고자 하는 원소가 mid에 있는 원소보다 작으므로 왼쪽 범위를 찾아야 한다는 뜻이 된다.
이때 이미 mid에 위치한 원소는 탐색했으므로 Right는 mid-1로 변경해서 조금이라도 탐색 횟수를 줄여준다.
Right=mid-1로 범위를 바꾼 뒤 다시 중앙값(mid)을 비교해보면 2를 찾을 수 있다.
해당 위치의 인덱스를 저장한 뒤 반복문을 빠져나오면 된다.
다음은 리스트에 없는 7을 찾아보겠다.
찾고자 하는 원소가 중앙값보다 크므로 오른쪽 범위에 있단 의미고 마찬가지로 중앙값은 탐색했으므로 탐색 횟수를 줄이기 위해 Left는 mid+1로 변경한다.
오른쪽 범위로 이동해서 다시 중앙값을 비교해보니 찾고자 하는 원소보다 중앙값이 더 크다.
이 말은 왼쪽 범위에 있단 뜻이므로 Right를 mid-1로 변경한다.
다시 왼쪽 범위로 이동해서 중앙값을 비교해보니 찾고자 하는 원소가 중앙값보다 더 크다.
이 말은 중앙값보다 오른쪽 범위에 있단 뜻이므로 Left는 mid+1로 변경한다.
이때 Left는 Right보다 커져서 역전되므로 결국 원소를 찾지 못한 채 반복문을 빠져나오게 된다.
이 알고리즘이 이진 탐색이며 7개의 Data에서 2를 찾는데 2번 연산, 7이 있는지 확인하는데 3번 연산밖에 하지 않았다.
만약 선형 탐색이었다면 최악의 경우 7번(Data의 크기만큼)의 연산을 할 것이고 확실히 이진 탐색을 통해 연산 횟수가 줄어든 것을 알 수 있다.
지금은 Data의 크기가 작기 때문에 몇 번 차이가 없지만 Data의 크기가 막대하게 커지면 상당히 효율적인 알고리즘이란 사실을 체감할 수 있을 것이다.
다음은 위의 설명대로 구현한 전체 코드이다.
data=[1,2,4,5,6,8,9]
def binary(n):
index=-1
left=0
right=len(data)-1
print("이진 탐색 과정 :",end=" ")
while left<=right:
mid=(left+right)//2
print(data[mid],end=" ")
if data[mid]==n:
index=mid
break
elif n<data[mid]:
right=mid-1
else:
left=mid+1
print()
return index
first=binary(2)
if first==-1:
print("없는 원소입니다.")
else:
print(first,"번째 인덱스에 있습니다.")
second=binary(7)
if second==-1:
print("없는 원소입니다.")
else:
print(second,"번째 인덱스에 있습니다.")
초기 Index는 -1로 지정하고 찾는 원소가 있다면 해당 원소의 인덱스로 갱신한다.
즉 여전히 Index가 -1이라면 찾는 원소가 없단 뜻이다.
그림을 참고하여 코드를 한 줄씩 따라가다 보면 쉽게 이해할 수 있을 것이다.
혹시나 해서 알고리즘 구현 자체를 접한 지 얼마 안 된 사람들께 덧붙이자면 이번 코드에서는 예시를 위해 인덱스를 반환하도록 구현했지만 당연하게도 각자 접하는 문제에 맞게끔 변형하여 구현해야 된다.
끝으로 이진탐색을 연습할 수 있는 문제를 몇가지 추천한다.
https://www.acmicpc.net/problem/1920
1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
https://www.acmicpc.net/problem/1654
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그
www.acmicpc.net
'알고리즘 > 자료구조 알고리즘 강의' 카테고리의 다른 글
| [알고리즘] 이진 탐색 트리(Binary Search Tree) (Python) (0) | 2021.12.18 |
|---|---|
| [자료구조] 힙(Heap) (Python) (0) | 2021.12.14 |
| [자료구조] 트리(Tree) 이진 트리(Binary Tree) 트리 순회 (Tree Traversal) (Python) (0) | 2021.12.09 |
| [자료구조] 스택(Stack)과 큐(Queue) 데크(Deque)까지 (Python) (0) | 2021.12.04 |
| [PDF 전자책] 쉽게 풀어쓴 자료구조와 알고리즘 기본 가이드 (0) | 2021.11.27 |
