[Algorithm] 이진 탐색(Binary Search)

이진 탐색(Binary Search)?

이진 탐색이란 데이터가 정렬되어 있는 상태에서 탐색 범위를 줄여나가며 특정한 값을 탐색하는 알고리즘으로, 탐색할 때마다 탐색 범위가 반으로 줄어들기 때문에 속도가 빠르다는 장점이 있다.

 

구현

코드

public class BinarySearch {

    public static void main(String[] args) {
        int[] array = {1, 3, 4, 6, 7, 9, 10, 11, 14, 16, 17, 20};
        int target = 16;

        int left = 0;
        int right = array.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;

            if (array[mid] == target) {
                System.out.println("mid = " + mid);
                System.out.println("array[mid] = " + array[mid]);
                break;
            }

            if (array[mid] < target) {
                left = mid + 1;
                continue;
            }
            right = mid - 1;
        }
    }
}

 

동작 과정

먼저 left를 0, right를 끝 지점(array.length-1)에 놓고 시작한다.

target값이 mid값보다 크므로 left를 mid + 1로 바꾸어 오른쪽으로 범위를 줄여준다.

아직까지 target값이 더 크므로 다시 left 값을 mid + 1의 값으로 바꾸어 범위를 줄여준다.

target값이 mid값보다 작으므로 right값을 mid - 1 값으로 바꾸어 왼쪽으로 범위를 줄여준다.

target값과 mid값이 같으므로 종료한다. (만약 찾고자 하는 값이 없을 때는 여기서 범위를 한 번 더 줄이면 left > right가 되므로 종료한다)

 

시간 복잡도

선형 탐색의 경우 O(n)이지만 이진 탐색의 경우 O(log n)이므로 대부분의 상황에서 이진 탐색이 더 빠르다. 먄약 선형 탐색으로 해결하기 어려운 문제 상황이 발생하면 이진 탐색을 고려해보자. (단, 이진 탐색은 정렬된 데이터라는 조건이 전제된다)

 

끝

이진 탐색에서 많이 실수하는 것이 탐색 범위 설정이다.

찾고자 하는 값이 들어있음에도 탐색 범위를 맞게 갱신하지 못하여 생기는 오류이다.

또한 일반적인 이진 탐색 뿐만아니라 중복된 값이 있을 때 값들의 경계점을 찾아야 하는 상황이 있을 수도 있다.

이에 대해 자세히 알고싶다면 상계(Upper Bound)와 하계(Lower Bound)에 대해 학습해보자.