알고리즘 : BinarySearch 이진 탐색

어제 해결하지 못 한 문제가 이진 탐색 문제였다.

그래서 오늘은 알고리즘을 스스로 구현해보며 이진 탐색 연습을 해야겠다는 생각이 들었다.

 

먼저 처음에 구현한 이진 탐색의 코드이다.

import java.util.Arrays;

public class BinarySearchTest {
	static int[] arr; // binarySearch에서 돌 배열
	static int cnt=0; // 일치하는 수가 몇 개 있는지 체크할 변수
	
	public static void binarySearch(int num, int idx, int min, int max) {
		if(arr[idx]==num) { // 일치하는 경우
			cnt++;
			return;
		}
		
		if(idx-min<2) {
			if(min==0 && arr[min]==num) cnt++;
			return;
		}
		
		if(max-idx<2) {
			if(max==arr.length-1 && arr[max]==num) cnt++;
			return;
		}
		
		if(arr[idx]>num) { // 찾는 수보다 해당 인덱스의 수가 더 큰 경우
			binarySearch(num, min+(idx-min)/2, min, idx);
		} else { // 찾는 수보다 해당 인덱스의 수가 더 작은 경우
			binarySearch(num, idx+(max-idx)/2, idx, max);
		}
	}

	public static void main(String[] args) {
		arr=new int[]{11, 91, 20, 2, 8, 59, 33, 10, 4};
		Arrays.sort(arr);
		
		int[] target= {10, 3, 4, 6, 2, 33};
		int n=arr.length-1;
		for(int i:target) { binarySearch(i, n/2, 0, n); }
		
		System.out.println(cnt);
	}

}

 

그러나 몇 번 테스트를 하다가 틀렸다는 것을 알 수 있었다.

이유는 idx-min<2 와 max-idx<2의 상황이 동시에 발생하는 경우가 있기 때문이다.

그래서 이 부분을 수정해주었다.

 

수정된 두 번째 코드이다.

public static void binarySearch(int num, int idx, int min, int max) {
	if(arr[idx]==num) {
		chk=true;
		return;
	}
		
	if(idx-min<2 || max-idx<2) {
		if(min==0 && arr[min]==num) chk=true;
		if(max==arr.length-1 && arr[max]==num) chk=true;
		return;
	}
		
	if(arr[idx]>num) {
		binarySearch(num, min+(idx-min)/2, min, idx);
	} else {
		binarySearch(num, idx+(max-idx)/2, idx, max);
	}
}

 

그러나 이 코드를 기반으로 이진 탐색 문제를 제출했더니 실패했다 .. 🥹

애초에 배열의 첫 요소와 마지막 요소를 제대로 안 돌기 때문에 문제가 된다는 생각이 들었다..

그래서 이번에는 아예 첫 요소와 마지막 요소를 다 돌 수 있도록 코드를 작성해보기로 했다.

 

먼저, 모두 돌 수 있도록 하려면 min과 max가 같아지는 순간이 존재해야 할 것이다. (0이나 마지막 요소의 경우)

그리고 코드를 다시 천천히 뜯어보며 생각해보니, 아예 idx를 매개 변수로 하지 않아도 될 것 같다는 생각이 들었다.

min과 max만으로도 가운데 자리를 찾을 수 있기 때문이다.

또한 모두 돌기 위해서는 num이 더 작은 경우 min이 min이고 현재 인덱스보다 1 작은 수가 max가 될 것이다.

반대로 num이 더 큰 경우 max는 max이고 현재 인덱스보다 1 큰 수가 min이 될 것이다.

만약 min이 max보다 커지는 경우 예외 처리를 해주면 될 것 같다.

 

그렇게 세 번째 코드.

package practice;

import java.util.Arrays;

public class BinarySearchTest {
	static int[] arr; // binarySearch에서 돌 배열
	static int cnt=0; // 일치하는 수가 몇 개 있는지 체크할 변수
	
	public static void binarySearch(int num, int min, int max) {
		if(max<min) return;
		
		int idx=min+(max-min)/2;
		
		if(arr[idx]==num) { // 일치하는 경우
			cnt++;
			return;
		}
		
		if(arr[idx]>num) { // 찾는 수보다 해당 인덱스의 수가 더 큰 경우
			binarySearch(num, min, idx-1);
		} else { // 찾는 수보다 해당 인덱스의 수가 더 작은 경우
			binarySearch(num, idx+1, max);
		}
	}

	public static void main(String[] args) {
		arr=new int[]{11, 91, 20, 2, 8, 59, 33, 10, 4};
		Arrays.sort(arr);
		
		int[] target= {10, 3, 4, 6, 2, 33};
		for(int i:target) { 
			if(arr.length<=0) break;
			binarySearch(i, 0, arr.length-1);
		}
		
		System.out.println(cnt);
	}

}

 

이진 탐색 코드를 수정하고, 현재는 필요없지만 예외 처리를 추가했다.

메인 메소드에서 binarySearch를 시작하기 전에, 기준인 arr가 만약 0보다 작거나 같은 경우 break로 시작조차 하지 않는 것이다.

 

이번 코드는 성공 !!

구현이 3트라니.. 😭 잊고 있었는데 다시 구현해보니 기억이 날 것 같다.

앞으로 잊지 않게 자주 사용해주어야겠군.

오늘의 알고리즘 공부는 여기서 끝!!!