[Python] 이진 탐색 알고리즘(1) 개요
순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해서 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정합니다. O(logN) 이진 탐색의 시간 복잡도 단계마다 탐색범위를 2로 나누는 것과 동일하므로 연산횟수는 log₂N 에 비례합니다. 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개 가량의 데이터만 남습니다. 2단계를 거치면 8개 가량의 데이터만 남습니다. 3단계를 거치면 4개 가량의 데이터만 남습니다. 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장합니다. 이진 탐색 소스코드: 재귀적..
Python/이코테
2022. 6. 19. 22:04
