이진 검색 과정을 출력하는 프로그램 작성하기

이진 탐색 과정을 출력하는 프로그램 작성하기

 

이진 탐색 과정 중, 현재 검색 중인 구간과 중앙요소를 표시해주는 프로그램을 작성하는 문제를 풀어보았다. 

(참고: "Doit 자료구조와 함께 배우는 알고리즘 입문 자바편" 117페이지의 연습문제다.)

 

 

완성된 실행 모습:

 

 

작성한 코드

프로그램의 구조는 다음과 같이 작성했다. 

 

- 실행부분인 메인메서드

- 이진 탐색을 수행하는 메서드: binSearch

- 구간을 표시하는 메서드: intervalDesign

 

 

ㅡ 메인메서드

먼저 메인메서드의 구조는 다음과 같다.

 

간단하다. 먼저 요솟수와 요소(정수) 내용을 Scanner로 입력받는다. 그리고 찾을 값을 입력하면 이진검색하는 메서드를 실행시킨다. 그리고 그 메서드가 반환한 인덱스를 기반으로, 원하는 값을 그 인덱스에서 찾았다며 알려주는 동작을 하고있다.

public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	
	System.out.println("요솟수:");
	int n = scan.nextInt();
	
	int[] a = new int[n];
	System.out.print("오름차순 요소: ");
	int inp = scan.nextInt(); a[0]=inp;
	for(int i=1; i<n; i++) {
		do {
			System.out.print("오름차순 요소:");
			a[i] = scan.nextInt();
		}while(a[i]<a[i-1]);
	}
	
	System.out.print("찾을 값: ");
	int key = scan.nextInt();
	System.out.println("이진 탐색을 시작합니다.");
	int indx = binSearch(a, key);
	
	if(indx!=-1) {
		System.out.print("\n원하는 값 "+key+"는 "+indx+"위치에 있습니다.");
	} else if (indx==-1) {System.out.println("\n찾는 값이 없습니다.");}
	else {System.out.println("생각 못한 경우");}		
}

 

 

ㅡ 이진탐색 메서드 binSearch

그럼 이제 이진탐색하는 메서드인 binSearch를 보겠다. 

이 메서드는 탐색완료 후 찾는 key값의 인덱스를 반환하도록 했다.

 

먼저 간단히 설명하겠다. 해당 배열과 찾는 키값을 인자로 받는다. 그리고 일단 이진탐색을 하기 전에, 콘솔창에 시각적으로 보여줄 프레임을 잡아준다. 그리고 나서 while문 속에서 이진탐색이 이루어지는데, 조건은 !(pl>pr)이다. 즉, 이진탐색을 하는 동안 구간이 변화됨에 따라 pl과 pr을 갱신해나가는데, 최종적으로 이진 탐색이 종료되어 pl과 pr의 크기가 역전될 때까지 이진탐색을 진행한다. 그리고 탐색을 진행함에 따라 현재 구간(pl~pr)과 중앙 요소(a[pc])가 무엇인지 시각적으로 보여주는 메서드인 intervalDesign을 끼워넣어주었다.

 

static int binSearch(int[] a, int key) {
	//인덱스 반환
	int n = a.length;
	int pl=0; int pr=n-1; int pc=(pr+pl)/2;
	
	System.out.printf("  |");
	for(int i=0; i<n; i++) {
		System.out.printf("%3d", i);
	}
	System.out.print("\n--+");
	for(int i=0; i<3*n+2; i++) {
		System.out.print("-");
	}
	intervalDesign(pl,pc,pr,a);
	while(!(pl>pr)) {
		if(key<a[pc]) { 
			pr=pc-1; pc=(pr+pl)/2; 
			intervalDesign(pl,pc,pr,a);
			}
		else if(key>a[pc]) { 
			pl=pc+1; pc=(pr+pl)/2; 
			intervalDesign(pl,pc,pr,a);
		}
		else if(key==a[pc]) {
			return pc;}
	}
	return -1;
}

 

 

ㅡ 구간을 시각적으로 보여주는 메서드 intervalDesign

이 문제가 요구한 '현재 이진검색 과정을 자세히 출력해 보여주기'에 해당하는 메서드다. 다음과 같이 작성했다.

 

두 가지 조건문으로 나누었다. 첫 번째는 'pl, pc, pr의 인덱스가 겹치지 않을 경우'이고, 두 번째는 'pl, pc, pr의 인덱스가 겹쳐서 구간 출력(<- + ->)이 불가능한 경우' 이다. 후자의 경우에는 그냥 <-, ->구간 표시 없이, 중앙 요소 위에 '+'만 표시해주도록 작성했다. 

 

static void intervalDesign(int pl, int pc, int pr, int[] a) {
	if(pc!=pr & pc!=pl) {
		//구간표시부
		System.out.print("\n  |");
		System.out.printf(String.format("%%%ds", pl*3+3), "<-");
		System.out.printf(String.format("%%%ds", pc*3-pl*3), "+");
		System.out.printf(String.format("%%%ds",  pr*3-pc*3), "->");
		System.out.printf("\n%2d|", pc);
		for(int i=0; i<a.length; i++) {
			System.out.printf("%3d",a[i]);
		} 
		
	}else if (pc==pr | pc==pl) {
		System.out.print("\n  |");
		System.out.printf(String.format("%%%ds", pc*3+3), "+");
		System.out.print("\n  |");
		for(int i=0; i<a.length; i++) {
			System.out.printf("%3d",a[i]);	
		}
	}
}

 

 

 

 

● 헤맸던 것:

  메소드 intervalDesign에서 구간을 나타낼 때였다. pr, pc, pl들이 겹칠 때를 미리 생각하지 못해서 이러한 경우는 뒤늦게 처리해주었다. 미리 생각하여 pc==pr인 케이스, pc==pl인 케이스를 염두에 두었으면 더 좋았겠다. 

 

 

---

답안과의 비교

큰 차이는 없었지만, "우왓 이렇게도 할 수 있구나!"하는 통찰을 얻었다. 

 

 

▶ 구조의 차이점:

 

- 방법의 차이점:

  pl과 pr의 선언만 do-while문 밖에다 하고, 실직적인 탐색이 이루어지는 do-while문의 맨앞에 pc의 갱신을 두었다. 나같은 경우는 do-while이 아닌 while문을 사용하였고 중앙요소의 갱신을 while문 안쪽에 하지 않았다. 나는 key와 중앙요소를 대소비교하는 각 조건마다 pc를 갱신했다. 그래야 intervalDesign의 인자에 갱신된 pc를 넣을 수 있었기 때문이다. 

 

 또한 나는 이진탐색 과정을 시각적으로 보여주는 intervalDesign메소드를 따로 두었지만, 답안에서는 이진탐색 메소드에 과정출력을 포함했다.

 

 

 

▶ 탐색과정을 보여주는 방법의 차이점:

 

  답안에서는 조건문을 적극 활용하여 '탐색 과정을 보여주는 부분'과 '탐색부분'을 독립적으로 조건실행하도록 했다. 또한 <- + ->를 출력하는 방법도 차이가 있었다. 답안에서는 <-에서 +까지 표시해주는 모양(간격)을 구간의 케이스(pl!=pc이냐 아니냐)에 따라 달리해주었다. 그리고나서 닫는부분인 ->의 간격도 케이스(pc!=pr이냐 아니냐)에 따라 다르게 조정했다.

 

 

참고: 다음은 답안에 있던 do-while문 속 이진탐색+과정보여주기 과정이다. 

 

do {
	int pc = (pl + pr) / 2; // 중앙요소의 index
	System.out.print("   |");
	if (pl != pc)
		System.out.printf(String.format("%%%ds<-%%%ds+", (pl * 4) + 1, (pc - pl) * 4), "", "");
	else
		System.out.printf(String.format("%%%ds<-+", pc * 4 + 1), "");
	if (pc != pr)
		System.out.printf(String.format("%%%ds->\n", (pr - pc) * 4 - 2), "");
	else
		System.out.println("->");
	System.out.printf("%3d|", pc);
	for (int k = 0; k < n; k++)
		System.out.printf("%4d", a[k]);
	System.out.println("\n   |");
	if (a[pc] == key)
		return pc; // 검색성공
	else if (a[pc] < key)
		pl = pc + 1; // 검색범위를 뒤쪽 절반으로 좁힘
	else
		pr = pc - 1; // 검색범위를 앞쪽 절반으로 좁힘
} while (pl <= pr);

 

---

꽤 재미있었다.