오름차순의 순서대로 정렬되어 있는 N개의 데이터에서 특정한 숫자가 몇 번째 위치에 있는지를 알아내는 프로그램을 작성하시오.
각 데이터 값의 범위는 정수범위이다.
첫 줄에 N이 주어진다. N은 정렬되어 주어지는 데이터의 수이다.(1≤N≤50,000)
둘째 줄에는 N개의 서로 다른 수가 정렬되어 주어진다. 각 수는 공백 하나로 분리되어 주어진다.
셋째 줄에는 데이터에서 찾아야할 특정한 수의 개수 T가 주어진다.
즉, T가 3이면 3개의 수를 정렬된 데이터에서 찾아야 한다.(1≤T≤10,000)
넷째 줄에는 T개의 수가 공백 하나로 분리되어 주어진다.
찾아야할 수가 정렬되어 주어진 데이터의 수중에서 앞에서부터 몇 번째에 있는지 그 위치를 출력한다.
첫 번째 위치는 1이다. 만약, 찾으려는 수가 주어지는 데이터에 존재하지 않는다면, 0을 출력한다.
7
2 4 9 10 14 23 32
3
6 23 9
0
6
3
탐색 알고리즘 중 이진 탐색을 이용한 탐색 결과를 출력하는 문제입니다.
이진 탐색은 정렬된 데이터에 대해서만 사용이 가능하고 정렬된 데이터의 중간 위치를 기준으로 데이터를 비교하고
해당 값이 검색하는 값보다 큰 경우 우측(중간 값 + 1 ~ 끝 값) 부분 데이터를
찾고자 하는 값이 중간 위치 값보다 작은 경우 좌측(시작 값 ~ 중간 값 - 1) 부분 데이터를 가지고 이진 탐색을 반복해 탐색을 하는 알고리즘으로
시간 복잡도는 빅O 표기법으로 나타냈을 때 O(log n) 입니다.
찾고자 하는 데이터가 없는 경우는 부분 데이터의 길이가 1보다 작아지는 순간이라고 생각할 수 있을 것 같습니다.
