[자료구조] 이진 탐색(이분 탐색)

이진 탐색은 일반적인 탐색 방법보다 빠르게 검색이 가능합니다.

다만 정렬이 되있어야한다는 단점을 가지고 있다.

배열안에 1부터 100까지의 숫자가 들어있다고 하자.

그리고 우리는 37이라는 숫자를 찾아야한다.

숫자 37을 찾으려면 3가지 방법이 있다.

하나는 37을 호출하는 방법 : 이 방법은 배열에 값을 넣고 그 값을 리턴 시켜주면 된다.

하지만 등차수열(일정하게 증가하는 수열) 그것도 1씩 증가하는 배열일때만 가능하다.

지금 같은 경우에는 이 방법이 가장 빠른 방법일지도 모르겠다.

시간 복잡도는 O(1) 즉, 엄청빠른 시간안에 문제를 해결할 수 있다.

두 번째 방법은 1부터 차례대로 찾는 방법이다.

이 방법같은 경우 O(n)이라는 시간이 걸린다. 

여기서 n은 100까지를 말하는데, 검색해야할 숫자가 100이라면 1부터 100까지 전부 확인해야 답을 구할 수 있다.

이 방법을 순차 탐색이라고 한다. (뭐 위 방법도 어떻게 보면 순차 탐색일 수도 있겠다. 왜냐하면 배열에 저장하고 그 값을 호출하기 때문이다.) 

마지막 방법은 바로 이진탐색이다.

먼저 가운대의 숫자를 골라야한다.

현실에서는 어떤 숫자를 사용해도 상관없지만 프로그래밍 상에서는 또, 다른 구현을 해줘야 하기 때문에 가장 무난한 가운데를 선택하는것이 좋다고 생각한다.

여기에서는 50이다. 그런데 우리가 찾는 값은 37이다. 그러면 가운데 값보다 우리가 찾는 값보다 크다.

그래서 뭔가의 조치가 필요한데

잘 생각해보면 50보다 큰 숫자는 어차피 쓸모없는 숫자다. 왜냐하면 우리가 찾는 값은 37이기 때문이다.

그러면 51~100까지의 숫자를 전부 지우면 된다.

그러면 왼쪽 값을 변경을 시켜야 할까?

오른쪽 값을 변경 시켜야할까? 현재 왼쪽 값은 1이고 오른쪽 값은 100이다.

바로 오른쪽 값을 변경시켜줘야한다. 왜나하면 51~100까지와 가까운 값은 100이기 때문이다.

그러면 오른쪽 값에 가운데에서 1을뺀값을 추가해주면 된다.

왜 1을 빼는가?

왜나하면 49를 검색할수 도 있는데 2를 빼게 되면 49를 영원히 검색이 불가능해질지도 모르기때문이다.

그러면 왜 더하지않는가? 왜나햐면 더하는 순간 51이 되버리는데 의미가 없기 때문이다.

(아무것도 안하는 경우 도 있긴 한데.... 사실 잘모르겠다. 컴퓨터는 0부터 시작해서 그런가? 더 했을때 쓸모없는 값이여서 그런가 ? : 51) 

자 그러면 계속해서

1 ~ 49 의 중간값 : 25 

26 ~ 49 중간값 ; 37

그러면 50 -> 25 -> 37 순으로 검색이 완료된다.

정확히 3번만에 값을 찾았다.

시간 복잡도는 O(logn)이 걸린다.

 

그러면 구현을 해보겠다.

특이하게 재귀를 사용해서 구현해 봤다.

import java.util.Scanner;

public class RecuireBineaeySearch {
	static int[] arr;
	static int ky;
	static int binerySearch(int left, int right) {
		
		if (left <= right) {
			int mid = left+right >>> 1;
			
			if (ky == arr[mid]) {
				return mid;
			} 
			
			if (ky < arr[mid]) {
				return binerySearch(left, mid-1);
			} else {
				return binerySearch(mid+1, right);
			}
			
		}
		
		return -1;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		arr = new int[n];
		
		for(int i = 0; i<n;i++) {
			arr[i] = sc.nextInt();
		}
		
		ky = sc.nextInt();
		int idx = binerySearch(0, n-1);
		System.out.println(idx);
	}
}

 

사실 이진 탐색을 순수한 탐색으로 문제를 해결하지 않는다.

어떤 문제는 값을 더해서 문제를 해결하고

또 어떤 문제는 값을 나눠서 문제를 해결한다.

어떻게 보면 단순히 이진탐색은 아이디어에 불과하다. 이 아이디어를 가지고 잘 접목시킨다면 문제를 잘 해결할 수 있을거라 생각한다.

ex) 나무 자르기 , 랜선 자르기 등등...