[이것이 취업을 위한 코딩 테스트다 with 파이썬] 5. 이진 탐색
·
Computer Science/자료구조 | 알고리즘
이진 탐색 알고리즘순차 탐색리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이진 탐색정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법시작점, 끝점, 중간점 이용 -> 탐색 범위 설정예시이미 정렬된 10개의 데이터 중 값이 4인 원소 찾기[Step 1] 시작점: 0, 끝점: 9, 중간점: 4 (소수점 이하 제거)[Step 2] 시작점: 0, 끝점: 3, 중간점: 1 (소수점 이하 제거)[Step 3] 시작점: 2, 끝점: 3, 중간점: 2 (소수점 이하 제거)시간 복잡도단계마다 탐색 범위를 2로 나누는 것과 동일 -> 연산 횟수는 $log_2N$에 비례ex. 초기 데이터 개수 32개 -> 이상적으로 1단계 거치면 16개가량의 데이터 남음2단계 ..
