이진 탐색 알고리즘. 순차 탐색과 이진 탐색의 정의

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다.

아이패드로 공부해놓고 블로그로 옮기면서 작성하는거 귀찮아서 미루다가 다시 업로드.

---

이진 탐색 알고리즘

순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법.
   >> 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정합니다.

 

 * 중간점의 경우 짝수는 5와 6으로 두 개가 될 수 있는데 이 경우, 소숫점 이하는 제거함.
  반 씩 좁혀가면서 찾아가는 개념. 

 

 이진 탐색의 시간 복잡도

 -단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 로그N에 비례한다.
 -예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개가량의 데이터만 남는다.
  > 2단계를 거치면 8개 가량의 데이터만 남는다.
  > 3단계를 거치면 4개 가량의 데이터만 남는다.
 다시 말해 이진 탐색은 탐색 범위를 반으로 줄이면서 시간 복잡도는 O(Log N)을 보장한다.

 

 bisect_left(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
 bisect_right(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환
 

 파라메트릭 서치
 > 최적화 문제를 결정 문제( 예 혹은 아니오 ) 로 바꾸어 해결하는 기법.
 예시 : 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제.
 일반적으로 코테에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다.

 

 

---