Binary Search 이분탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

for(int i=0; i<8; i++){
  if(arr[i] == 9){
    cout << "찾았다!";
  }
}

이분탐색 (이진탐색) 이란?

❗️정렬되어 있는 리스트❗️에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

이분탐색은 시작점, 끝점, 중간점을 이용해 탐색 범위를 설정한다.

배열 [2, 4, 6, 8, 3, 1, 7, 9] 에서 값이 7인 원소를 찾아야 할 때?

배열을 정렬한다.
- 이분탐색은 꼭! 정렬된 리스트에서만 사용!
- [1, 2, 3, 4, 6, 7, 8, 9]
이분 탐색 시작!
- 시작점 idx = 0, 끝점 idx = 7
  그럼 중간점은 ? idx = (시작점 + 끝점) / 2 (소수점 버리면) => 3
- arr[3]의 값은 뭐지? 4네? 우리가 찾는 값 7보다 작으므로
- arr[3] 다음 원소가 시작점이 됨 (arr[4])
- 만약 중간점 값이 우리가 찾는 값보다 작다면,
  더 이상 중간값 앞에 있는 값들은 볼 필요가 없으므로
  중간값 다음의 원소가 시작점이 됨 (시작점 = 중간점 + 1)
- 만약 중간점 값이 우리가 찾는 값보다 크다면,
  더 이상 중간값 뒤에 있는 값들은 볼 필요가 없으므로
  중간값 전의 원소가 끝점이 됨 (끝점 = 중간점 - 1)
이분탐색 계속하기
- 시작점 idx = 4, 끝점 idx = 7
- 중간점 = (4 + 7) / 2 = (소수점 버리면) => 5
- arr[5]의 값은? 7
- 찾았다!

순차 탐색에 비해 시간 복잡도가 훨씬 적음 (O(log2N))
순차 탐색은 최악의 경우(모든 원소 탐색 시)(O(N))

최적화 문제를 결정 문제 (예 / 아니오) 로 바꾸어 해결하는 기법

일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이분 탐색을 이용하여 해결할 수 있음.
(최적화 문제 : 문제의 조건에 맞는 특정 변수의 최솟값 혹은 최댓값을 구하는 문제)

Q. 다음과 같이 나이 순으로 정렬된 사람들이 있다. 그리고 25살 이상이라면 소주를 좋아한다는 것이 증명되어 있다고 한다. 그럼 이 중에서 소주를 좋아하는 나이가 가장 어린 사람은 누구인가?

물론 가장 간단한 방법은 맨 앞에서부터 “너 소주 좋아해?”라고 물어보면서,
처음으로 “네!”라고 대답하는 사람을 찾는 것이다.
하지만, 파라메트릭 서치를 이용해 최적화 문제를 결정 문제로 바꾼다면,
log시간안에 문제를 풀어낼 수 있다.

최적화 문제? 결정 문제?

이분 탐색은 O(log2N) 이라는 경이로운 시간 복잡도를 가지고 있습니다. 당연히 N이 엄청 크게 들어오겠죠?
최적화 문제에 마주쳤는데 N이 엄청나게 크다 ⇒ 파라메트릭 서치 기법을 적용해 이분탐색으로 풀어보는게 좋습니다.