[필수 알고리즘] 이진탐색

이진탐색이란?

- 어떤 값을 찾을때 정렬의 특징을 이용해 빨리 찾음

- 정렬이 되어 있을 경우, O(N) -> (logN)

- 기존 다른 방법으로 시간 복잡도를 생각했을때, 안되면 이진탐색으로 처리하면 좋음

 

첫 아이디어

- M개의 수마다 각각 어디에 있는지 찾기

- for : M개의 수

- for : N개의 수안에 있는지 확인

 

첫 시간복잡도

- for : M개의 수 > O(M)
- for : N개의 수안에 있는지 확인 > O(N)

- O(MN) = 1e10 > 시간초과 

 

아이디어

- M개를 확인해야는데, 연속하다는 특징 활용 가능(투포인터)? => 연속하지 않아 불가

- 정렬해서 이진탐색 가능?

(N개의 수 먼저 정렬)

(M개의 수 하나씩 이진 탐색으로 확인)

 

시간 복잡도

- N개의 수 정렬 : O(N * lgN)

- M개의 수 이진탐색 : O(M*lgN)
- O((N+M)lgN) = 2e5 * 20 = 4e6 => 가능

 

*4개일때 2번 만에 탐색 2^x, 8개 일때 3번 만에 탐색 2^3으로 해서 lgN으로 취

 

자료구조

- 탐색 대상 수 : int[]

- 탐색 하려는 수 : int[]

 

이진탐색(무조건 외워야하는 함수)

 public static int Search(int start, int end, int target, List<int> nums)
{
    if (start == end)
    {
        return nums[start] == target ? 1 : 0;
    }

    int mid = (start + end) / 2;

    if (nums[mid] < target)
    {
        return Search(mid + 1, end, target, nums);
    }
    else
    {
        return Search(start, mid, target, nums);
    }
}

- start, end값을 반으로 나눠 target보다 작으면 +1로 해서 재귀 실행 아니라면 바로 탐색 실행하는 방식

 

문제풀이

- 백준 1920

 

1.

class num_1920
{
    static void Main(string[] args)
    {
        // 빠른 입출력을 위한 설정
        var sr = new System.IO.StreamReader(Console.OpenStandardInput());
        var sw = new System.IO.StreamWriter(Console.OpenStandardOutput());

        int n = Convert.ToInt32(sr.ReadLine());
        List<int> nums = Array.ConvertAll(sr.ReadLine().Split(), int.Parse).ToList();

        int m = Convert.ToInt32(sr.ReadLine());
        List<int> target_nums = Array.ConvertAll(sr.ReadLine().Split(), int.Parse).ToList();


        //정렬해야 이진탐색 가능
        nums.Sort();

        for (int i = 0; i < target_nums.Count; i++)
        {
            sw.WriteLine(Search(0, n - 1, target_nums[i], nums));
        }

        sw.Flush();
        sr.Close();
        sw.Close();
    }

    public static int Search(int start, int end, int target, List<int> nums)
    {
        if (start == end)
        {
            return nums[start] == target ? 1 : 0;
        }

        int mid = (start + end) / 2;

        if (nums[mid] < target)
        {
            return Search(mid + 1, end, target, nums);
        }
        else
        {
            return Search(start, mid, target, nums);
        }
    }
}

- 빠른 탐색을 위한 StreamReader(Console.OpenStandardInput())와 StreamWriter(Console.OpenStandardOutput()) 사용

- nums를 정렬 한 후 target값을 돌며 있는지 탐색하여 출력 

 

참고영상

- 바로가기