이진탐색

1295 : 이진탐색

제한시간: 1Sec    메모리제한: 32mb
해결횟수: 882회    시도횟수: 1923회   

오름차순의 순서대로 정렬되어 있는 N개의 데이터에서 특정한 숫자가 몇 번째 위치에 있는지를 알아내는 프로그램을 작성하시오.

 

첫 줄에 N이 주어진다. N은 정렬되어 주어지는 데이터의 수이다.(1≤N≤50,000)

둘째 줄에는 N개의 서로 다른 수가 정렬되어 주어진다. 각 수는 공백 하나로 분리되어 주어진다.

셋째 줄에는 데이터에서 찾아야할 특정한 수의 개수 T가 주어진다. 즉, T가 3이면 3개의 수를 정렬된 데이터에서 찾아야 한다.(1≤T≤10,000)

넷째 줄에는 T개의 수가 공백 하나로 분리되어 주어진다.

찾아야할 수가 정렬되어 주어진 데이터의 수중에서 앞에서부터 몇 번째에 있는지 그 위치를 출력한다. 첫 번째 위치는 1이다. 만약, 찾으려는 수가 주어지는 데이터에 존재하지 않는다면, 0을 출력한다.

[Copy] 7 2 4 9 10 14 23 32 3 6 23 9

[Copy] 0 6 3

위의 JUNGOL에서 해당 문제를 풀기 위해서 이진탐색을 해야했습니다.

친절하게도 제목부터 이진탐색이라고 하지 않았으면. 찾아야 하는 수를 데이터에 있는 수를 하나하나 비교를 했을 겁니다.

물론 입력 데이터 수가 최대 50,000개라서 제한시간에서 탈락이 될거라는건 알겠지만 우선 해보았겠죠.

그렇지만 친절하게 제목에서 저렇게 저걸로 풀어라고 하는 문제다 보니 이진탐색이 뭔지 찾아 보았습니다.

개념자체는 외부지형에서 흔히쓰이는 쿼드트리처럼 큰 덩어리로 필요없는 부분은 버리고 필요한 부분이 있는 곳으로 다시 가서

또 필요 없는 부분은 버리고 하는 식으로 찾아가는 그런 분할 알고리즘이었습니다.

아래는 위키백과의 이진탐색 알고리즘의 내용입니다.

그런데 내용처럼 꼭 오름차순이 아니더라도 상관은 없을것 같지만 오름차순이 알고리즘짜기엔 더 편하겠죠.

이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.

 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다.

 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다.

 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. 이진 검색은 분할 정복 알고리즘의 한 예이다.

예로 아래 그림에서 9 7 6 4 3 2 1 이 있고 6을 찾으려고 할때 발생하는 상황들입니다.

먼저 7개의 데이터의 중간인 4번째값인 4를 기준으로 6과 비교를 합니다.

비교를 해보니 6이 더큽니다.

이 데이터는 내림차순이라 찾고자 하는 값이 왼쪽에 있을것입니다.

그래서 다시 왼쪽을 기준으로 분할합니다.

4번째가 제일 작은 값이 될테고 0번째가 제일 큰값이 될겁니다.

그럼 다시 반으로 쪼개면 2번째 값인 7과 비교를 합니다.

찾으려는 값6보다 7이 큽니다.

6보다 7이크니 2번째가 큰값이 있는 곳이고 4번째가 작은 곳이 있는 곳이니 

그 중간은 3번째가 되겠죠.

3번째 있는 값을 보니 찾고자 하는 값인 6이므로 알고리즘을 그만 합니다.

아래에는 위키의 의사 코드입니다.

위쪽 코드는 재귀함수를 이용한 예이고 아래는 반복문을 활용한 예입니다.

BinarySearch(A[0..N-1], value, low, high)
 {
  if (high < low)
    return -1 // not found
  mid = (low + high) / 2
  if (A[mid] > value)
    return BinarySearch(A, value, low, mid-1)
  else if (A[mid] < value)
    return BinarySearch(A, value, mid+1, high)
  else
    return mid // found
}
 
 
 
 
/*high와 low를 지정*/
binarySearch(A[0..N-1], value)//k
{
  low = 0
  high = N - 1
  while (low <= high)
 {
      mid = (low + high) / 2
      if (A[mid] > value)
          high = mid - 1
      else if (A[mid] < value)
          low = mid + 1
      else
          return mid // found k
  }
  return -1 // not found k
}

아래는 실제 코드입니다.

int binarySearch( int f, int data[], int s, int e )
{
    if( s>e )
        return -1;
 
    int mid = (e+s)/2;
 
    if( f<data[mid] )
         return binarySearch( f, data, s, mid-1 );
    else if( f>data[mid] )
         return binarySearch( f, data, mid+1, e );
    return mid;
}

찾고자 하는 값보다 중간 값이 크면 중간값까지만 찾으면 되니 mid-1이고,

찾고자 하는 값보다 중간 값이 작으면 찾고자 하는 값은 중간값 다음 부터 찾으면 되니 저런 식으로 합니다.

하지만 찾고자 하는 값이 없을 수가 있으니 그럴땐 s와 e의 값을 보고 s>e일땐 리턴을 시켜줍니다.

찾고자 하는 값이 없을 경우 그 부근을 계속 탐색할텐데 그럴때 s가 e보다 커지는 경우가 나오고 종료 합니다.