[알고리즘] 이진 탐색(Binary Search)이란

1. 이진 탐색(Binary Search)이란?

이진 탐색은 이분 탐색이라고도 합니다. 순차적 탐색, 선형 탐색(Linear Search)보다 속도가 빠릅니다.

순차적 탐색은 0부터 9까지 숫자가 있다면 0, 1, 2, 3, 4...9까지 총 10번의 탐색을 실행합니다.
그에 비해 이진 탐색은 이분(二分)이라는 말처럼 반으로 나누어서 탐색을 합니다.

이진 탐색에서 찾아야 하는 숫자가 9라고 했을 때 0부터 9까지 있다면 중간값부터 탐색을 하게 됩니다.
0과 9의 중간값인 4를 찾고, 목표인 9가 중간값인 4보다 크기 때문에 5와 9의 중간값을 다시 찾습니다.
다음 중간값인 7과 9를 비교해보면 9가 더 크고, 마지막으로 다음 중간값 8보다 9가 크므로 9를 찾아 탐색을 종료합니다.

 

0

1

2

3

4

5

6

7

8

9

 

0

1

2

3

4

5

6

7

8

9

 

0

1

2

3

4

5

6

7

8

9

 

0

1

2

3

4

5

6

7

8

9

 

 

 

//반복문으로 구현

public int binarySearch(int[] arr, int n) {
    int first = 0;
    int last = n-1; //n은 전체 길이
    int mid = -1;

    while(first <= last) {
        mid = (first+last)/2;

        if(target == arr[mid])
            return mid;
        else if(target < arr[mid])
            last = mid-1;
        else
        	first = mid+1;
    }
    
    return mid;
}

 

//재귀로 구현

public int binarySearch(int[] arr, int target, int first, int last) {
	int mid = (first + last) / 2;
        
    if (target == arr[mid])
        return mid;
	else if (target < arr[mid])
        return binarySearch(arr, n, left, mid-1);
	else if (target > arr[mid]) 
        return binarySearch(arr, n, mid+1, last);	
    else 
    	return -1; //찾는 타겟이 없을 때
}

 

 

 

2. 이진 탐색의 시간복잡도

순차적 탐색: 최악의 경우 n을 전부 탐색해야 하므로 O(n)

이진 탐색: 중간값에 따라 n/2를 반복하므로 O(log2)

 

데이터 수가 적은 게 아니라면 웬만한 경우에서는 이진 탐색의 속도가 더 빠릅니다.