알고리즘) 이진 탐색 알고리즘

순차 탐색 : 리스트 안에 있는 데이터를 탐색하기 위해 앞에서부터 하나씩 확인하는 방법

이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

-> 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정

-> 중간점이 두개인 경우 보통 소수점 이하를 제거하여 낮은 값으로 사용

 

단계마다 탐색 범위를 2로 나누는 것과 동일하기 때문에 시간 복잡도는 O(logN)

 

파이썬 이진 탐색 라이브러리

특정 범위에 속하는 데이터 개수 구하기

 파라메트릭 서치 => 최적화 문제를 결정 문제로 바꾸어 해결하는 기법

-> 최대한 값을 낮추거나 높일 때 여러번의 결정 문제를 해결하면서 최적 값을 찾는 경우

-> 특정 조건을 만족하는 가장 알맞는 값을 찾는 최적화 문제

-> 일반적으로 이진 탐색으로 해결 가능

-> 탐색의 범위가 크면 일단 이진 탐색부터 생각해보자