[C++/탐색] 정렬된 2차원 배열에서 탐색하기

• 입력 : 첫 줄에 n (n = 1, 2 4 8 16, 32, 64, 128, 256, 512, 1024)과 정수 k가 주어지고, 다음 줄부터 각 행의 n개의 값이 차례로 주어진다.
  • 특이하게 각 행의 값들과 각 열의 값들이 오름차순으로 정렬되어 주어진다.
• 출력 : 배열에 있는 값 중에서 k 값이 (i, j)에 있다면 i j를 차례로 출력하고 없다면 -1을 출력한다. (행과 열은 모두 0부터 시작한다.) 단, k 값이 두 개 이상 있다면 , 사전 순서로 가장 작은 (i, j)값을 출력한다.
  • 사전 순서는 (a, b), (c, d) 두 위치에 대한 사전 순서는 a < c이면 (a,b)가 앞서는 것이고, a==c)인 경우에는 b와 d중에서 작은 값을 갖는 것이 앞서는 것이다.
  • 첫 번째 샘플 입력에서 -4가 (1,3),(2,1),(3,0) 모두 세 곳에 등장한다. 사전 순서로 따지면 행 번호가 갖 ㅇ작은 (1,3)이 가장 앞서기에 (1,3)을 출력하면 된다.
  •  

---

정렬된 배열에서 값 찾기는 Binary_search 를 이용하면 된다. 좌,우 끝 인덱스를 기준으로 중앙 인덱스를 정하고 중앙인덱스와 찾으려는 값과 비교하여 상황에 따라서 출발점과 끝점을 이동시켜 탐색하는 과정이다. 이는 한 줄을 모두 탐색하는데 거리는 시간 O(n)보다 O(logn)으로 시간복잡도 면에서 성능이 뛰어나다. 

문제를 해결하면서 각 행마다 binary_search를 적용하여 찾으려는 값과 동일한 인덱스를 추출하고 각 인덱스를 사전순으로 나열해 정답을 출력하는 방식으로 하였다.

 

전체 소스코드

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

using namespace std;

const int MAX = 1025;
int arr[MAX][MAX];
int n,k;
int b_search(int idx,const long long find_num)
{
    int s = 0;
    int e = n-1;
    while(s<=e)
    {
				if(arr[idx][s]==find_num)
						return s;
				if(arr[idx][e]==find_num)
						return e;
        int m = (s+e)/2;
        if(arr[idx][m]==find_num)
            return m;
        else if(arr[idx][m]>find_num)
            e = m-1;
        else if(arr[idx][m]<find_num)
            s = m+1;
    }
    return 100002;
}
int main()
{
    cin>>n>>k;

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>arr[i][j];
        }
    }


    int x=100002,y=100002;
    for(int i=0;i<n;i++)
    {
        int temp = b_search(i,k);
        if(temp!=100002)
        {
            if(i<y)
            {
                y = i;
                x = temp;
            }
        }
    }
    if(x==100002&&y==100002)
        cout<<-1<<endl;
    else
        cout<<y<<" "<<x<<endl;

    return 0;
}

/*
binary_search를 이용하여 탐색하였습니다. 각 행마다 binary_search로 탐색하여 
(y,x) y가 작은 값을 먼저 찾고
만약 같은 행에 찾는 값이 있다면 x값이 더 작은 값을 출력하도록 하였습니다.
binary_serach는 log n의 수행시간을 가지고 행의 갯수n만큼 수행하니
O(nlogn) 수행시간으로 해결하였습니다,
*/