한 번에 많은 데이터를 탐색하는 알고리즘
순차탐색의 시간복잡도 : O(N)
데이터의 개수가 N개일 때 최대 N번의 비교 연산을 필요로 하므로 최악의 경우 시간 복잡도는 O(N)이다.
이진탐색의 시간복잡도 : O(logN)
단계를 거칠 때 마다확인하는 원소가 절반씩 줄어든다.(반으로 쪼개면서 탐색을 하기 때문에) 2로 나누는 것과 동일하므로 시간 복잡도는 O(logN)이다.
이진탐색 | Binary search
구현 방법
- 재귀 함수
- 반복문
데이터의 위치를 나타내는 변수 : start (시작점) / mid (중간점) / end (끝점)
핵심 | 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것
1) 재귀함수
def binary_search(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2
if array[mid] == target:
return mid
elif array[mid] > target:
return binary_search(array, target, start, mid - 1)
else:
return binary_search(array, target, mid + 1, start)
n, target = map(int, input().split())
array = list(map(int, input().spllit()))
result = binary_search(array, target, 0, n-1)
if result == None:
print("해당 원소 없음")
else:
print(result + 1)
2) 반복문
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 None
n, target = map(int, input().split())
array = list(map(int, input().spllit()))
result = binary_search(array, target, 0, n-1)
if result == None:
print("해당 원소 없음")
else:
print(result + 1)
핵심 코드
elif array[mid] > target:
end = mid - 1중간점의 원소값이 타겟 보다 큰 경우, 중간점 기준 오른쪽은 타켓이 없기 때문에 볼 필요가 없다. 따라서 끝점을 중간점 왼쪽(mid - 1) 인덱스로 지정해준다.
즉, 오른쪽 데이터를 날려버림!
else:
start = mid + 1 중간점의 원소값이 타겟 보다 작은 경우, 중간점 기준 왼쪽은 타켓이 없기 때문에 볼 필요가 없다. 따라서 시작점을 중간점 오른쪽(mid + 1) 인덱스로 지정해준다.
즉, 왼쪽 데이터를 날려버림!
코딩 테스트 이진탐색
- 탐색 범위가 큰 상황에서의 탐색 문제
처리할 데이터의 개수나 값이 매우 크면 O(logN)의 속도를 내야하는 알고리즘 을 떠올려야 문제를 풀 수 있는 경우가 많다.
입력 데이터의 개수가 많은 문제에서 동작 속도 해결
input() 함수를 사용하면 동작 속도가 느려 오답 판정을 받을 수 있다.
이 경우 sys 라이브러리의 readline() 함수를 사용하면 시간 초과를 피할 수 있다.
import sys
input_data = sys.stdin.readline().restrip()주의 사항
- rstrip() 함수를 호출하지 않으면 readline() 입력 후 엔터가 줄 바꿈 기호로 입력되는데, 이 공백 문자가 제거 되지 않는다. 따라서 꼭 호출 해주어야 한다.
