이진 탐색 ( Binary Search )

( 참고 출저 : https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6 )

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

     정렬된 리스트안에 중간점의 값과 목표한 값을 비교하고,
     중간점의 값이 목표한 값보다 크다면,
     시작점과 중간점의 사이에서 탐색을 하게되고,

     중간점의 값이 목표한 값보다 작다면,
     중간점과 끝점 사이에서 탐색을 하는 것을 반복한다.

     그렇게되면 결국 중간값은 목표한 값과 같아지게되는 탐색법이다.
     탐색범위를 절반씩 줄이기 때문에 시간복잡도는 O(log N)을 보장한다.
     
 
 : 파라매트릭 서치 ( Parametric Search )
     최적화 문제를 결정 문제 ( "예" 혹은 "아니오") 로 바꾸어 해결하는 기법
     예시 : 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
     일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다

     

     이진 탐색 알고리즘이 워낙 강력한 탓인지 두가지만 배워보았다.

     이진 탐색 자체를 구현하는 것은 어렵지 않았으나, 이를 활용해 찾는 값의 범위를 구하는 방법은
     구현할때 처음에 막막했다.
     좌측 끝과 우측 끝을 나누어서 찾는 아이디어를 얻고나서 스무스하게 해결했다.
     물론 강의에서 알려준 코드가 훨씬 간단했다..