이분탐색, 파라메트릭 서치

개요

절반으로 나누어 탐색.
두 개의 파티션으로 분할된 구간에서 분할 경계의 위치를 찾는 방법.

설명

• 원하는 데이터를 찾고자 할때, 전체를 순차적으로 탐색하는 것이 아니라, 절반씩 나누어 가며 찾는다.
  N의 크기가 충분히 작고, 시간이 충분하다면 O(N)시간에 기존방식으로 탐색이 가능하다.
  하지만 N이 충분히 크고, 시간적 제한이 존재한다면 O(logN)시간에 탐색이 가능한 이분탐색을 사용하자.
  단, 정렬이 선행되어야 한다.

기존 방식

67이라는 Value를 찾는다고 가정하자.
기존의 방식이라면 배열을 순회하며 찾아야 한다.
O(N)의 시간복잡도를 가진다.

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

int main()
{
	vector<int> arr = { 10,20,23,25,40,61,66,67,70,80 };
	int target = 67;
	bool flag = false;
	for (int i = 0; i < arr.size(); ++i)
	{
		if (arr[i] == target)
			flag = true;
	}
}

이분탐색

67이라는 값을 찾는다고 하자.

• Step1. 데이터가 정렬되어 있지 않다면, 우선 정렬한다.
  

• Step2. 중간값과 찾고자 하는값을 비교한다. 동일하다면 종료
  - 중간값(40) 이 찾고자 하는값(67)보다 작다. 찾고자 하는 범위를 변경한다.
  

• Step3. 중간값을 기준으로 다시 반으로 나누어 Step2를 수행.
  - 중간값 67을 찾았다.
  

Parametric Search

이분탐색과 동일한 원리를 가진다.
이진탐색과 비슷하나, 주어진 범위 내에서 원하는 값 또는 조건에 가장 일치하는 값을 찾아내는 알고리즘.
최적화 문제(문제의 상황을 만족하는 특정 변수를 찾는 문제)를 결정 문제로 바꾸어 푸는 것

• 가정 : 25세 이하는 맥주만 먹는다.
• 사람이 5명 있다. 각 사람의 나이는 20, 22, 27, 28, 33이다. 이 중 맥주만 먹는 사람 중 가장 나이가 많은 사람은 몇 살 인가?

와 같은 문제가 있다고 하자. 이진탐색과 동일한 접근으로 구할 수 있다.

C++의 upperbound, lowerbound

c++의 경우, 각 함수를 통해, 해당 값이 정렬을 해치지 않으며 어느 위치에 들어갈 수 있을지 찾아준다.

• upper_bound : 들어갈 수 있는 위치 중 가장 마지막
• lower_bound : 들어갈 수 있는 위치 중 가장 처음
  가장 마지막, 가장 처음이라는 말이 있는 이유는 데이터에 중복된 값이 있을 수 있기 때문이다.

// arr[1]=1, arr[2]=2, ... , arr[n]=n 일 때
    int ub = *upper_bound(arr, arr + N, 65); // 66
    int lb = *lower_bound(arr, arr + N, 60); // 60

코드

• Java 및 C++

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int[] arr;
	static int N;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = 1001;
		arr= new int[N];
		for (int i = 1; i < N; i++)
			arr[i] = i;

		int target = Integer.parseInt(in.readLine());

		int left = 1;
		int right = N-1;

		while (left <= right)
		{
			//중앙값 초기화
			int mid = (left + right) / 2;

			if (mid == target)
			{
				System.out.println("Find");
				break;
			}
			else if (mid > target)
			{
				right = mid - 1;
			}
			else
			{
				left = mid + 1;
			}
		}
	}
}

C++

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

#define N 1001
using namespace std;

int arr[N] = { 0, };
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

    for (int i = 1; i < N; i++)
        arr[i] = i;

    int target; // 타겟 값
    cin >> target;

    int left = 1;
    int right = N-1;

    while (left <= right)
    {
        //중앙값 초기화
        int mid = (left + right) / 2;

        if (mid == target)
        {
            cout << "Find!" << '\n';
            break;
        }
        else if (mid > target)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }

    return 0;
}