이진 탐색

데이터가 정렬된 상태에서 데이터의 크기를 절반씩 줄이면서 대상을 찾는 알고리즘

 

중앙값을 비교하여 절반씩 줄여가므로 시간복잡도는 O(logN) 이 필요하다.

 

위와 같은 배열이 있을때 35를 찾아야한다고 가정해보자

앞에서부터 순차적으로 탐색하게될시 6번의 탐색 과정이 필요하다.

 

이진탐색 과정을 살펴보자

 

① 중간값 15 보다 크므로 오른쪽을 다음 탐색범위로 지정

② 중간값 23 보다 크므로 오른쪽을 다음 탐색범위로 지정

③ 중간값 35 로 탐색대상 확인

 

문제

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

1920번: 수 찾기

 

풀이

using System.Text;

StringBuilder sb = new StringBuilder();

int count = int.Parse(Console.ReadLine());
long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);

Array.Sort(nums);

int searchCount = int.Parse(Console.ReadLine());
long[] searchNums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);

for (int i = 0; i < searchCount; i++)
{
    BinarySearch(searchNums[i]);
}

System.Console.WriteLine(sb.ToString());

void BinarySearch(long target)
{
    int start = 0;
    int end = count-1;

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

        if(nums[mid] == target)
        {
            sb.AppendLine("1");
            break;
        }

        if(start >= end)
        {
            sb.AppendLine("0");
            break;
        }

        if(nums[mid] < target)
            start = mid+1;

        else if(nums[mid] > target)
            end = mid-1;
    }
}

 

잘못된부분이나 개선될수있는 부분은 댓글 남겨주시면 감사합니다.