이진 탐색 (binary-search)

오름차순, 혹은 내림차순으로 이미 정렬이 되어있는 배열에서 특정한 값을 찾아내는 것.

방식은 배열 중간의 임의의 값을 선택하여 찾고자 하는 키 값과 비교하는 것을 반복하는 방식으로 진행되며, 크기가 작고 큰지에 대해 이후 탐색해야할 배열의 영역을 정해 다시 탐색한다. 해당 값을 찾을 때 까지 이러한 과정을 반복하게 되며, 따라서 탐색 배열은 한 번 탐색이 끝날 때 마다 배열의 크기가 절반씩 줄어든다고 볼 수 있다. 

 

가령 N개 크기의 배열을 이진 탐색하면 N은 *1/2, *1/4 식으로 줄어들 것이다. 여기서 몇 번 탐색했느냐가 시간복잡도를 나타내게 된다. 따라서 이를 수식으로 세운다면 시간복잡도는 log2N이 된다고 볼 수 있다(2^X(실행탐색회수)=N)

 

public class BinSearch {
	//요솟수가 n인 배열 a에서 key와 같은 요소를 이진검색한다
	static int binSearch(int[] a, int n, int key){
		int pl = 0;			//검색 범위의 첫 인덱스
		int pr = n - 1;		//검색 범위의 끝 인덱스 
		
		do{
			int pc = (pl + pr)/2;	//중앙 요소의 인덱스
			if(a[pc] == key)
				return pc;			//검색 성공!
			else if (a[pc] < key)
				pl = pc + 1;		//검색 범위를 뒤쪽 절반으로 좁힘
			else
				pr = pc -1;			//검색 범위를 앞쪽 절반으로 좁힘
		}while (pl <= pr);
		
		return -1;					//검색 실패!
	
		}
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		System.out.print("요솟수 :");
		int num = stdIn.nextInt();
		int[] x = new int[num]; //요솟수가 num인 배열
		
		System.out.print("오름차순으로 입력하세요.");
		
		System.out.print("x[0]:");
		x[0] = stdIn.nextInt();	// 첫 요소 입력
		
		for(int i=1; i< num; i++){
			do{System.out.println("x["+i+"]:");
			x[i] = stdIn.nextInt();
			}while (x[i]< x[i-1]);		//바로 앞 요소보다 작으면 다시 입력
		}
		
		System.out.print("검색할 값 :");	//키 값 입력
		int ky = stdIn.nextInt();
		
		int idx = binSearch(x, num, ky);	//배별 x에서 키 값이 ky인 요소를 검색
		
		if( idx == -1)
			System.out.println("그 값의 요소가 없습니다.");
		else
			System.out.println(ky+"은(는) x["+ idx +"]에 있습니다.");
	}
}