8. 이진탐색 (binary search)

p. 180~194(9일차)

강의: 05-3

---

1. 이진탐색

- 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘

- 대상 데이터의 중앙값과 찾고자 하는 값을 비교한다.

  * 크기를 절반씩 줄이면서 대상을 찾음

 

✔ 핵심 이론

- 이진탐색은 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복한다.

 ✔ 과정

1)  현재 데이터셋의 중앙값을 선택

2) 중앙값 > 타깃 데이터, 중앙값 기준으로 왼쪽 데이터셋을 선택

3) 중앙값 < 타깃 데이터, 중앙값 기준으로 오른쪽 데이터셋을 선택

4) 1) ~3) 과정을 반복, 중앙값 == 타깃데이터면 종료

 

 ✔ 백준 1920번  - 원하는 정수찾기

 ✔ 문제 이해

- X라는 정수가 존재하는지 알아내자

- 첫 줄 : 데이터 개수, 두번째 줄: 찾아야 할 숫자 개수

- N과 M의 최대 범위 100,000

  * 단순 반복문으로 처리 불가

- 이진탐색을 사용하면 O(nlogn)으로 해결

 

 

 ✔ 코드 입력 / 정리