이진(이분) 탐색이란?

살펴보는 범위를 절반 씩 줄여가며 답을 찾는 탐색임
따라서 정렬이 되어있어야 함

ex) A부터 Z까지 책이 정렬이 되어있을 때 Cook이라는 책을 찾고싶음
내가 임의로 책 하나를 골랐는데 그게 Y로 시작하는 책이면 내가 고른 그 책 포함 그뒤로는 다 제끼고 남은책들 중에서 고르면됨
이런식으로 반복해 나가는게 이진탐색

파라메트릭 서치

최적화 문제를 결정 문제로 바꿔서 이진탐색으로 푸는 방법

• 최적화 문제 : 문제상황을 만족하는 변수의 최대,최소값을 구하는 문제
• 결정 문제 : Yes or No 문제

예를 들어 사람들이 나이순대로 쭉 있고 대통령 선거투표를 할 수 없는 사람 중 가장 나이많은사람을 찾고싶다(최적화 문제) -> 모든 사람들을 투표 가능하면 Yes, 못하면 No 로 바꾸어 푼다(결정 문제)

보통 문제가 주어지면 이것이 True인지 False인지 구분하는 함수를 만들어서 진행함

그래서 Parameter가 주어지면 True or False로 바꿔서 범위를 반씩 줄여가며 가운데 값이 True인지 False인지 구함