[C++] 이분 탐색(Binary Search)

이분 탐색(Binary Search)

선형 자료구조가 정렬되어 있을 때 특정한 값을 빠르게 찾는 방법이다.

 

이분 탐색(O(logN)) vs 선형 탐색(O(N))

 

문제

 

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int N, M;
	int a[100000];

	cin >> N;
	for (int i = 0; i < N; ++i)
		cin >> a[i];
	cin >> M;

	sort(a, a + N);

	for (int i = 0; i < M; ++i) {
		int target;
		cin >> target;

		int start = 0, end = N - 1, mid;
		while (start <= end) {
			mid = (start + end) / 2;

			if (target == a[mid]) {
				cout << "1\n";
				break;
			}
			else if (target > a[mid])
				start = mid + 1;
			else if (target < a[mid])
				end = mid - 1;
		}

		if (start > end)
			cout << "0\n";
	}
}

 

https://leetcode.com/problems/search-in-rotated-sorted-array/submissions/

Search in Rotated Sorted Array - LeetCode

#include <vector>
using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target)
                return mid;
            else if (nums[left] <= nums[mid]) // mid를 기준으로 왼쪽과 오른쪽 중 정렬된 부분에서 확인
            {
                if (nums[left] <= target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            else
            {
                if (nums[mid] < target && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }

        return -1;
    }
};

 

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Find First and Last Position of Element in Sorted Array - LeetCode

#include <vector>
using namespace std;

class Solution
{
public:
    vector<int> searchRange(vector<int> &nums, int target)
    {
        vector<int> answer;
        int start = 0, end = nums.size() - 1;
        while (start <= end)
        {
            if (nums[start] == target && nums[end] == target)
            {
                answer.push_back(start);
                answer.push_back(end);
                break;
            }
            else if (nums[start] < target)
                start++;
            else
                end--;
        }

        if (answer.empty())
        {
            answer.push_back(-1);
            answer.push_back(-1);
        }

        return answer;
    }
};

 

문제 : 파라메트릭 서치(Parametric Search)

이분 탐색을 응용하여 최솟값이나 최댓값을 찾는 문제이다.

 

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int K, N;
	long long LAN[10000];

	cin >> K >> N;
	for (int i = 0; i < K; ++i)
		cin >> LAN[i];

	long long start = 1, end = *max_element(LAN, LAN + K), mid;
	while (start <= end) {
		mid = (start + end) / 2;

		long long cnt = 0;
		for (int i = 0; i < K; ++i)
			cnt += LAN[i] / mid;

		if (cnt >= N)
			start = mid + 1;
		else
			end = mid - 1;
	}
	cout << end;
}

 

https://www.acmicpc.net/problem/1300

1300번: K번째 수

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int N, K;
	cin >> N >> K;

	int start = 1, end = K, mid;
	while (start <= end) {
		mid = (start + end) / 2;

		int cnt = 0;
		for (int i = 1; i <= N; ++i)
			cnt += min(N, mid / i);

		if (cnt >= K)
			end = mid - 1;
		else
			start = mid + 1;
	}
	cout << start;
}

 

https://www.acmicpc.net/problem/3079

3079번: 입국심사

#include <iostream>
#include <algorithm>
using namespace std;

long long t[100000];

int main()
{
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
        cin >> t[i];

    long long start = 1, end = *max_element(t, t + N) * M, mid;
    while (start <= end) {
        mid = (start + end) / 2;

        long long num = 0;
        for (int i = 0; i < N; ++i)
            num += mid / t[i];

        if (num >= M)
            end = mid - 1;
        else
            start = mid + 1;
    }
    cout << start;
}

 

https://www.acmicpc.net/problem/1939

1939번: 중량제한

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int N, M, V1, V2;
vector<pair<int, int>> graph[10001];

bool bfs(int mid)
{
	queue<int> q;
	bool ck[10001]{};

	q.push(V1);
	ck[V1] = true;
	while (!q.empty()) {
		int tv = q.front();
		if (tv == V2)
			return true;
		q.pop();

		for (int i = 0; i < graph[tv].size(); ++i) {
			int nv = graph[tv][i].first, nw = graph[tv][i].second;
			if (!ck[nv] && nw >= mid) {
				q.push(nv);
				ck[nv] = true;
			}
		}
	}
	return false;
}

int main(void)
{
	cin >> N >> M;

	int start = 1e9, end = 0, mid = 0;
	for (int i = 0, A, B, C; i < M; ++i) {
		cin >> A >> B >> C;
		graph[A].push_back({ B,C });
		graph[B].push_back({ A,C });

		start = min(start, C);
		end = max(end, C);
	}
	cin >> V1 >> V2;

	while (start <= end) {
		mid = (start + end) / 2;

		if (bfs(mid))
			start = mid + 1;
		else
			end = mid - 1;
	}
	cout << end;
}

 

https://www.acmicpc.net/problem/2585

2585번: 경비행기

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;

    pair<int, int> point[1002]{};
    for (int i = 1; i <= n; i++)
        cin >> point[i].first >> point[i].second;
    point[n + 1] = { 10000,10000 }; // 목적지

    int start = 1, end = 15000, mid;
    while (start <= end) {
        mid = (start + end) / 2;

        bool flag = false;

        queue<pair<int, int>> q;
        q.push({ 0,0 }); // 출발지
        bool ck[1002]{};
        ck[0] = true;
        while (!q.empty()) {
            int tn = q.front().first;
            int tk = q.front().second;
            q.pop();

            if (tn == n + 1) {
                flag = true;
                break;
            }

            for (int i = 1; i <= n + 1; i++) {
                int dist = pow((point[tn].first - point[i].first), 2) + pow((point[tn].second - point[i].second), 2);
                if (!ck[i] && mid * mid > dist && tk <= k) {
                    ck[i] = true;
                    q.push({ i,tk + 1 });
                }
            }
        }

        if (flag)
            end = mid - 1;
        else
            start = mid + 1;
    }
    cout << start / 10 + (start % 10 ? 1 : 0);
}

 

문제 : 삼분 탐색

 

https://www.acmicpc.net/problem/8986

8986번: 전봇대

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<long long> v;

long long Sum(long  long dist)
{
	long long sum = 0;
	for (int i = 0; i < N; ++i)
		sum += abs((i * dist) - v[i]);
	return sum;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	v.resize(N);
	for (int i = 0; i < N; ++i)
		cin >> v[i];

	long long start = 0, end = v[N - 1];
	while (start + 3 <= end) {
		long long mid1 = (start * 2 + end) / 3;
		long long mid2 = (start + end * 2) / 3;

		if (Sum(mid1) < Sum(mid2))
			end = mid2;
		else
			start = mid1;
	}

	long long ans = 1e18;
	for (int i = start; i <= end; ++i)
		ans = min(ans, Sum(i));
	cout << ans;
}