알고리즘: 이분탐색(Binary Search)

이분 탐색의 개념

1부터 20까지의 수가 있다고 가정하자, 여기서 13을 찾아내려고 할 때,

아무 생각을 하지 않고 코드를 작성하면 단순히 for문을 통해 for(int i = 1; i < 21; i++) 로 찾게 될 것이다.

찾고자 하는 값이 1, 2처럼 시작점과 가까운 값이라면 시간 효율이 나쁘지 않겠지만,

18, 19와 같이 끝자락에 있는 수라면, 시간 효율이 극악이다.

사실 20이라는 작은 범위 내에서는 거기서 거기지만,

(눈으로도 그냥 가능하다)

백의 자리, 천의 자리로 넘어가면 사람의 눈으로 빠르게 판단하는 데에는 불가능하고, 

십만, 백만, 천만 등 그 수가 기하급수적으로 커지게되면 컴퓨터 역시 시간효율이 좋은 방법을 찾아내야 한다.

 

이 때 사용하는 탐색 방법이 이분 탐색이다.

 

이분 탐색의 원리

원리는 이렇다.

오름 차순이든 내림 차순이든 배열을 정리하고,

찾고자 하는 값을 N으로 둘 때, 첫 번째 index의 값과 마지막 index의 값 그리고 그 가운데 값을 지정해 두고,

n이 가운데 값보다 작으면 가운데보다 큰 값들을 모두 지워버리고 (라고 하지만 가운데 값을 마지막 index값으로 지정하고, 다시 가운데 값을 첫 번째 index 값과 마지막 index 값을 통해 지정하는) 왼쪽 값들에서 n을 찾는다.

public static int binarySearch(int[] list, int n){
	int first = 0;
    int last = list.length-1;
    
    int mid = (first+last)/2;
    
    while(last-first>=0){
    	if(list[mid] == n){
        	return mid;
        } else if( list[mid] < n){
        	first = mid+1;
        } else {
        	last = mid-1;
        }
        mid = (first+last)/2;
    }
}

약간 이런 느낌이라고 볼 수 있다.

이를 반복하면서 값에 범위를 제한한다.

단순한 방법으로는 N 개의 수 안에서 최대  N번을 수행해야하는데,

이분 탐색으로는 logN번이면 충분하다.

값이 확 줄게 된다!