[C++] 이분검색

📄문제

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는프로그램을 작성하세요.

 

⬇️ 입력

첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.
두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

8 32 23 87 65 12 57 32 99 81

 

⬆️ 출력

첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.

3

 

📝 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int N, M;
	scanf_s("%d %d", &N, &M);

	vector<int> arr(N);
	for (int i = 0; i < N; ++i)
		scanf_s("%d", &arr[i]);

	sort(arr.begin(), arr.end());

	int idx = N / 2;
	while (true)
	{
		// 현재 idx의 원소값이 찾고자 하는 값보다 크면?
		if (arr[idx] > M)
			idx = idx / 2;
		// 현재 idx의 원소값이 찾고자 하는 값보다 작으면?
		else if (arr[idx] < M)
			idx = (idx + N) / 2;
		else
		{
			printf("%d", idx + 1);
			break;
		}
	}
}

• 정렬된 arr에서 자신이 찾고자 하는 값이 arr[idx]보다 크다면, idx의 범위는 현재 idx부터 마지막 끝까지 범위 중 중간이 됩니다.
• 반대로, 찾고자 하는 값이 arr[idx]보다 작다면, idx는 현재 idx부터 맨 앞까지 범위 중 중간이 됩니다.
• 이를 반복하여 arr[idx] == M이라면, 검색이 끝난 것 입니다.

 

// lt, mid, rt를 명시하여 구현

int lt = 0, rt = N - 1, mid;

while (true)
{
    mid = (lt + rt) / 2;

    if (arr[mid] == M) // 값을 찾았다면?
    {
        printf("%d", mid + 1);
        break;
    }
    else if (arr[mid] > M) // 현재 값이 찾고자 하는 값보다 크면? -> mid를 감소
    {
        rt = mid - 1;
    }
    else // 현재 값이 찾고자 하는 값보다 작으면? -> mid를 증가
    {
        lt = mid + 1;
    }
}

• 이분검색의 정석대로 lt, rt, mid라는 변수를 명시하여 구현한 방법입니다.