검색 알고리즘 - 이진 검색

오늘은 검색 알고리즘 중에 이진 검색에 대해 알아보자.

📘 이진 검색이란?

이진 검색은 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘이다.
이진 검색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있다.

일단 이 알고리즘을 적용하는 전제 조건은 데이터가 이미 키 값으로 정렬(sort)되어 있을때만이다.
이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다.

✏ 이진 검색 원리

오름차순으로 정렬된 데이터에서 38을 검색하는 과정을 생각해보자.
먼저 배열의 중앙에 위치한 a[5]의 33부터 검색을 시작한다.
검색하려는 값인 38은 중앙 요소(a[5])보다 큰 값이다. 그러므로 검색 대상을 뒤쪽에 있는 5개(a[6] ~ a[10])으로 줄일 수 있다.

그 다음 검색 범위의 중앙에 위치한 요소인 a[8]이 원하는 값인지 확인한다.
검색하려는 값인 38보다 뒤쪽에 존재하기 때문에 검색 대상을 앞쪽의 2개(a[6] ~ a[7])으로 좁힐 수 있다.
이때 두 요소의 중앙 요소는 38이나 54중 아무거나 선택해도 무방하지만 여기선 앞쪽의 값 38을 선택하여 원하는 값인지 확인한다.
38은 원하는 키의 값과 일치하므로 검색 성공이다.

✏ 이진 검색 코드

간단한 코드로 사용법을 알아보자.

import java.util.Scanner;

public class Main {

    static int binSearch(int[] a, int n, int key) {
        int left = 0;           // 검색 범위의 첫 인덱스
        int right = n - 1;      // 검색 범위의 끝 인덱스

        do {
            int center = (left + right) / 2;    // 중앙 요소의 인덱스
            if (a[center] == key)       // 검색 성공
                return center;
            else if (a[center] < key)   // 키 값이 더 크다면 검색 범위를 뒤쪽 절반으로 좁힘
                left = center + 1;
            else                        // 키 값이 더 작다면 검색 범위를 앞쪽 절반으로 좁힘
                right -= center - 1;
        } while (left <= right);

        return -1;      // 검색 실패
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("요솟수 : ");
        int num = sc.nextInt();
        int[] a = new int[num];     // 요솟수가 num인 배열열

       System.out.println("배열 요소를 입력(오름차순) : ");

        System.out.print("a[0] : ");    // 첫 요소 미리 입력
        a[0] = sc.nextInt();

        for (int i = 1; i < num; i++) {
            do {
                System.out.print("a[" + i + "] : ");
                a[i] = sc.nextInt();
            } while (a[i] < a[i - 1]);      // 바로 앞의 요소보다 작으면 다시 입력 (오름차순)
        }

        System.out.print("검색할 키값 : ");
        int key = sc.nextInt();

        int idx = binSearch(a, num, key);

        if (idx == -1)
            System.out.println("그 값의 요소는 없습니다.");
        else
            System.out.println(key + "값은 a[" + idx + "]에 있습니다.");
    }
}

이진 검색의 시간 복잡도는 평균적으로 O(log n)이다.

✏ 이진 검색 종료 조건

아래의 조건 두 가지중에 하나만 성립하면 종료된다.

❶ a[center]와 key값이 일치하는 경우
❷ 검색 범위가 더 이상 없는 경우