실력키우기 이진탐색(JAVA)

1295 : 이진탐색

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

오름차순의 순서대로 정렬되어 있는 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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

/**************************************************************     Problem: 1295     User: a132034     Language: Java     Result: Success     Time:835 ms     Memory:29832 kb ****************************************************************/     import java.util.Scanner;      public class Main {     private static Scanner sc;     public static void main(String[] args) {          sc = new Scanner(System.in);          int N, T;          int []arrN;          int []arrT;                 N = sc.nextInt();          arrN = new int[N];          for(int i = 0 ; i < N; ++i)              arrN[i] = sc.nextInt();                 T = sc.nextInt();          arrT = new int[T];          for(int i = 0 ; i < T; ++i)              arrT[i] = sc.nextInt();                 //start Search          for(int i = 0 ; i < T; ++i){              binSearch(arrN, 0, N-1, arrT[i], i);          }                         }                public static void binSearch(int[] arr, int start, int end, int searchNum, int index)     {         if(end < start)         {             System.out.println(0);             return;         }                     //중간값을 찾음.          int mid = (start+end)/2;          if(arr[mid] == searchNum){              System.out.println(mid+1);              return;          }          else if(start == end){              System.out.println(0);              return;          }          else if(arr[mid] < searchNum)              binSearch(arr, mid+1, end, searchNum, index);          else              binSearch(arr, start, mid-1, searchNum, index);         return;     } }

이진탐색(binary search)은 정렬이 된 리스트에서 특정한 값을 찾는 알고리즘이다. 

Divde & Conquer 알고리즘으로 볼 수 있다. 

방법은 다음과 같다. 

1. 찾으려는 값(searchNum)을 배열의 중간 값과 비교한다. 

2. 더 큰 경우 중간 값 보다 큰 배열에서 1번을 수행하며, 작은 경우 중간 값 보다 작은 배열에서 1번을 수행한다.

3. 찾으려는 값이 있는 경우 출력하고, 찾으려는 값이 없는 경우(start == end 또는 start < end) 0을 출력한다. 

이진 탐색은 정렬이 되있다면 검색속도가 매우 빠르다는 장점이 있다. 2^50정도의 배열이 있더라도 50회 정도의 비교로 값을 찾을 수 있다. 

Big-O notation으로 표기할 경우 O(log n)정도의 복잡도를 가진다.