이진 탐색(Binary Search)과 매개변수 탐색(Parametric Search)

이진탐색이란?

---

이진 탐색이란 정렬된 배열에서 타겟의 존재 여부와 존재한다면 해당 위치를 알려주는 알고리즘이다. 중요한 점은 정렬된 배열에서만 사용할 수 있다는 것이다

 

기존의 단순 비교를 통한 탐색을 한다면 최악의 경우 배열 안에 있는 N개의 데이터 모두와 비교해야하므로 시간복잡도가 O(N)인 반면, 이진탐색은 재귀적으로 탐색범위를 반으로 줄여나가서 시간복잡도가 O(logN)까지 줄일 수 있다

 

 

이진탐색과 매개변수 탐색

---

매개변수 탐색(parametric search)이란?

*최적화 문제를 *결정 문제로 풀 수 있는 기술로 다음과 같은 상황에 이용할 수 있다.

    *최적화 문제(Optimization Problem): 가능한 해들 중 가장 좋은 해를 찾는 것

    *결정 문제(Decision Problem): 답이 이미 결정되었다고 보고 문제를 푸는 것

1. 결정문제로 풀면 쉽게 문제를 풀 수 있을 때

2. 어떤 시점까지는 조건을 만족하지만 그 후로는 조건을 만족하지 않는 경우 조건을 만족하는 최대값 찾기

3. 어떤 시점까지는 조건을 만족하지 않지만 그 후로는 조건을 만족하는 경우 조건을 만족하는 최소값 찾기

 

작동 방식

시간복잡도는 이진 탐색과 마찬가지로 탐색 배열의 크기를 반으로 줄이면서 탐색하므로 O(logN)이다

1. 배열에 가운데 위치한 숫자 X를 함수에 대입해 조건을 만족하는지 알아본다.

2. 조건을 만족한다면 X보다 큰 값 중에서, 조건을 만족하지 않는다면 X보다 작은 값 중에서 1의 과정을 반복한다

3. 더 이상 살펴 볼 배열이 남아있지 않는다면 알고리즘을 끝낸다

 

예시

놀이공원에 학생들이 키 순으로(오름차순) 줄을 서있다고 하자. 롤러코스터는 신장 150cm 이상만 탈 수 있다고 할 때, 최대 몇 명이 탈 수 있는지 구해보시오

키순으로 줄 서 있는 학생들

0. 결정문제로 바꾸어보자

-> 롤러코스터를 탈 수 있는 키인가? Yes/No -> Boolean 함수

 

1. 배열에 가운데 위치한 숫자 X를 함수에 대입해 조건을 만족하는지 알아본다.

2-1. 조건을 만족하지 않으므로 4번보다 큰 사람들에게 1의 과정을 반복한다

    - 전제에서 키순으로 정렬되어 있으므로 4번 이하의 사람들은 모두 정답 범위에서 벗어나게 된다

2-2. 조건을 만족하므로 6번보다 작은 사람들에게 1의 과정을 반복한다

3. 더 이상 살펴 볼 배열이 남아있지 않으므로 알고리즘 종료

    - left==right==mid이므로 더 이상 살펴 볼 배열 없음

    - 최종 탑승 가능 인원 8-6+1 = 3명