[알고리즘] 이진 탐색(binary search)

yujamint·2022년 7월 26일

Java ps 알고리즘

PS

목록 보기

6/9

이진 탐색(Binary Search)

이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 탐색 범위를 두 부분으로 분할하면서 찾는 방식으로, 처음부터 끝까지 돌면서 탐색하는 것보다 훨씬 빠르다는 장점을 갖고 있다.

탐색 과정

n개의 원소를 담고 있는 배열 arr에서 특정값 m을 찾는다

배열을 정렬한다. 이진탐색은 정렬된 배열에만 사용 가능한 알고리즘이다.
변수 low의 초기값은 배열의 첫 인덱스인 0, high의 초기값은 배열의 끝 인덱스인 n-1 로 잡는다.
변수 mid는 low와 high에 의거해 (low + high) / 2의 값을 가진다.
배열의 mid 인덱스 원소와 찾으려고 하는 m의 값을 비교한다. (arr[mid]와 m 비교)
m의 값이 arr[mid]보다 크다면 low = mid + 1, arr[mid]보다 작다면 high = mid - 1 로 값을 변경한다.
- 값을 변경함으로써 탐색 범위가 반으로 줄어든다.
low가 high보다 커질 때까지 3~5번 과정 반복

low는 탐색 범위의 최소값이고, high는 탐색 범위에서의 최대값이다. 비교 결과에 따라 low의 값을 높이거나 high의 값을 줄이면 탐색 범위가 줄어들게 되는데, mid와 m을 비교함으로써 탐색 범위를 반으로 줄여나가는 것이다.

이진 탐색 Java 코드

void binarySearch() {
    int[] arr = {23, 87, 65, 12, 57, 32, 99, 81};
    int m = 32; // 배열에서 32를 찾는다.
    int index = -1; // 정렬 후 m의 인덱스 번호

    Arrays.sort(arr); // 이진 탐색 실행하기에 앞서 배열 오름차순 정렬

    int low = 0, high = arr.length-1;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == m) { // m을 찾았을 떄
            index = mid;
            break;
        }
        else if (arr[mid] < m) // mid 인덱스의 원소가 m보다 작을 때
            low = mid + 1;
        else // mid 인덱스의 원소가 m보다 클 때
            high = mid - 1;
    }
    System.out.println(index); // 2 출력
}

배열(arr) : 23 87 65 12 57 32 99 81
구하려는 값(m) : 32

배열을 정렬한다.
결과 : 12 23 32 57 65 81 87 99
1회전 : low=0, high=7 -> mid=3, arr[mid]=57
57은 32보다 크기 때문에 57보다 작은 원소 중에서 32를 찾기 위해 high를 mid-1로 줄인다.
2회전 : low=0, high=2 -> mid=1, arr[mid]=23
23은 32보다 작기 때문에 23보다 큰 원소 중에서 32를 찾기 위해 low를 mid+1로 늘린다.
3회전 : low=2, high=2 -> mid=2, arr[mid]=32
32를 찾았으므로 index에 2를 할당하고 종료한다.

만약, 배열에 없는 33을 찾는다고 가정해보자.
2회전까지의 과정은 같고, 3회전부터 보도록 하겠다.

3회전 : low=2, high=2 -> mid=2, arr[mid]=32
32는 33보다 작기 때문에 32보다 큰 원소 중에서 33을 찾기 위해 low를 mid+1로 늘린다.
4회전 : low=3, high=2 -> low가 high보다 커졌기 때문에 m을 찾는 데에 실패하고 함수 종료

low가 high보다 커질 때까지 실행하는 것은 위의 예시와 같이 찾으려고 하는 값이 배열에 없을 때 무한으로 while문이 돌아가는 것을 막기 위한 조건이다.