본문 바로가기
추가 공부/알고리즘 & 코딩테스트

[Java] 이진검색(BinarySearch)

by shyun00 2023. 4. 19.

이진 검색은 데이터가 키 값으로 이미 정렬되어 있을 때 적용할 수 있는 알고리즘이다.

이진검색의 시간복잡도는 O(log N) 이다.

전체 범위를 탐색하는 선형 검색과 달리 검색 범위를 1/2로 줄여가면서 찾아가는 방법이다.

 

아래와 같이 7개의 요소를 가지는 배열에서 값이 23인 요소의 인덱스를 찾는 과정을 살펴보자.

1. 먼저 중앙값을 검색한다.

2. 중앙값과 타겟값을 비교한다.

    중앙값인 15가 타겟인 23보다 작으므로 값이 작은 왼쪽 부분은 탐색하지 않고 오른쪽 부분만 탐색한다.

    만약 타겟이 15였다면 더 이상 검색을 하지 않고 종료되었을 것이다.

    이처럼 크기 비교 결과에 따라 검색 범위가 달라지므로 이미 정렬되어 있는 대상에만 적용할 수 있다.

3. 타겟을 찾을때까지 1과 2의 과정을 반복한다.

위 예시에서는 두번만에 바로 타겟값을 찾을 수 있었다.

 

이 과정을 자바 코드로 작성하면 아래와 같다.

public class BinarySearch {

    // arr은 검색하고자하는 배열이며 target은 검색할 값이다.
    // 만약 타겟이 배열에 있으면 해당 인덱스를 출력하고 없을 경우 -1을 출력한다.
    public static int binarySearch(int[] arr, int target) {

        // 검색 범위를 설정하기 위해 오른쪽, 왼쪽 인덱스를 구해준다.
        int rightIdx = arr.length - 1;
        int leftIdx = 0;

        // 양 끝 인덱스를 기준으로 가운데 인덱스를 구해준다.
        // 가운데 인덱스에 해당하는 값과 타겟값을 비교하여 결과를 도출한다.
        do {
            int midIdx = (rightIdx + leftIdx) / 2;

            if (arr[midIdx] == target) return midIdx;
            else if (arr[midIdx] < target) leftIdx = midIdx + 1;
            else rightIdx = midIdx - 1;

        } while (leftIdx <= rightIdx);

        return -1;
    }

    public static void main(String[] args) {
        int output = binarySearch(new int[]{2, 5, 8, 15, 20, 23, 31}, 23);
        System.out.println(output); // 결과값: 5
    }
}