이진 탐색 개념 . 1

이진 탐색은 정렬되어 있는 리스트에서 특정한 데이터를 빠르게 탐색할 수 있도록 해주는 탐색 알고리즘이다

 

 

 

[ 이진 탐색 예시 ]

 

 

중간점을 구할 때 소수점 이하는 제거한다.

 

 

 

끝점이 중간점 왼쪽으로 움직여 새로운 끝점이 된다 

 

 

 

시작점이 중간점 오른쪽으로 움직여서 새로운 시작점이 된다.

 

 

 

 

 

 

이진탐색 파이썬 예시 1 :  재귀함수 버전

 

 

 

이진탐색 파이썬 예시 2 :  반복문 버전

 

 

 

 

C++에서는 하나의 배열 정보를 받을 때 1. 포인터를 사용하거나 2. vector 라이브러리를 사용하되 
별도로 변수를 카피하지 않고 이미 존재하는 vector 변수의 래퍼런스를 전달해야 한다
만약 &(앰퍼샌드)를 빼주게 되면 이 함수를 호출할 때 기존 vector에 담겨 있던 값을 카피하기 때문에
시간복잡도가 O(N)이 된다. 그렇기 때문에 반드시 vector를 넘겨줄 때는 래퍼런스를 넘겨줘야 한다

 

 

 

 

 

파이썬에서 유용한 함수

파이썬에서 bisect_left() 와 bisect_right() 은  C++ 의 upper_bound() ,  lower_bound() 와 사실상 같다

 

 

이진 탐색을 활용해야 하는 문제가 출제되는 경우 파라메트릭 서치 유형으로 문제가 출제되는 경우가 많다
최적화 문제란 어떤 함수의 값을 가능한 최대한 낮추거나 높이거나 하는 등의 문제이다.

파라메트릭 서치는 최적화 문제를 바로 해결하기 어려운 경우 그 문제를

여러 번의 결정 문제( '예' 혹은 '아니오' )로 바꾸어서 해결하는 방법이다  (문제 형태를 바꾸어서 해결하는 기법)