[백준 1920] 수 찾기

이분탐색(Binary Search)으로 해결하는 전형적인 문제입니다.

이분탐색(Binary Search)은 정렬되어 있는 배열에서 원하는 데이터를 찾고자 할 때,
배열 전부를 차례대로 훑어가며 찾는 것이 아니라 탐색 범위를 절반씩 줄여가면서 찾는 방법입니다.
다음의 예시를 봅시다.

<예시>
정렬되어 있는 배열 A = [1,2,3,4,5,6,7]이 존재할 때 2를 찾아보도록 합시다.
맨 먼저 양 끝의 인덱스를 start와 end로 설정합니다. 즉, start = 0이고 end = len(A) - 1 = 6이 됩니다.
이때 이 둘의 가운데에 위치한 값을 mid로 설정합니다. 즉, mid = (start + end) // 2 = 3이 됩니다.
그 후, 배열의 인덱스가 mid인 값과 찾고자 하는 값을 비교합니다. 즉, A[mid]와 찾고자 하는 값 2를 비교합니다.
이때, 배열 A가 ‘정렬’되어 있다는 사실에 주목합시다.
Case는 총 3가지로 나뉘게 됩니다.
- Case 1. A[mid]가 찾고자 하는 값과 같으면,
그대로 출력하면 됩니다.
- Case 2. A[mid]가 찾고자 하는 값보다 작다면,
찾고자 하는 값은 적어도 mid라는 인덱스보다 더 큰 인덱스에 존재합니다.
- Case 3. A[mid]가 찾고자 하는 값보다 크다면,
찾고자 하는 값은 적어도 mid라는 인덱스보다 더 작은 인덱스에 존재합니다.
각각의 케이스에 따라 start와 end를 조절하여 계속해서 범위를 절반씩 줄여나가면 됩니다.
값이 발견되면 탐색 성공, start가 end를 넘어설 때까지 발견되지 않는다면 값이 존재하지 않음을 의미합니다.

위의 예시가 이분탐색의 기본 원리를 그대로 설명하고 있습니다.
따라서, 위의 개념을 아래의 코드로 그대로 적용해볼 수 있습니다.
이때, 이분탐색은 정렬된 배열에서만 사용할 수 있기 때문에
미리 입력받은 숫자들의 배열을 sort()를 통해 정렬한 뒤 탐색을 시작합니다.
또한 for문을 통해 찾아야 하는 값들을 전부 탐색해주도록 합시다.

문제 : 백준 1920 - 수 찾기