[JAVA] 이진 검색(Binary Search)

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

---

이진 검색

이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다는 장점이 있다.

하지만 이진 검색은 데이터가 키 값으로 이미 정렬되어 있다는 전제 조건이 있어야 한다.

이진 검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.

시간 복잡도 측면에서 선형 검색은 O(N)이지만 이진 검색은 O(log N)을 가지므로 이진 검색이 훨씬 효율적인 알고리즘이다.

 

아래와 같은 배열에 오름차순으로 정렬된 데이터에서 39를 찾는 과정을 예로 들면, 먼저 배열 중앙에 위치한 5번째 인덱스부터 검색을 시작한다. 

인덱스 5의 값은 31은 39보다 작으므로 검색 대상을 뒤쪽 5개로 좁힐 수 있다.

그런 다음 검색 범위의 중앙에 위치한 인덱스 8이 원하는 값인지 확인한다.

인덱스 8의 값은 68이므로 검색 대상을 앞쪽 2개로 좁힐 수 있다.

이 때 두 요소의 중앙 요소는 39나 38중 아무거나 선택해도 상관 없지만 앞쪽의 값 39를 선택하여 원하는 값인지 확인한다.(6과 7의 중앙값은 (6+7) / 2 = 6이다 (정수의 나눗셈은 나머지를 버리기 때문))

39는 원하는 키의 값과 일치하므로 검색 성공이다.

static int binSearch(int[] arr, int key) //while문으로 구현
{
    int startptr = 0;
    int endptr = arr.length -1;
    int midptr = (startptr + endptr) / 2;
    while(startptr <= endptr) //시작 지점이 끝 지점보다 크면 루프 종료
    {
        midptr = (startptr + endptr) / 2;
        if(arr[midptr] == key) return midptr; //발견 함
        else //발견 못함
        {
            if(key > arr[midptr]) startptr = midptr + 1; //키가 배열 뒷 쪽에 있음
            else endptr = midptr -1; //키가 배열 앞 쪽에 있음
        }
    }
    return -1; //찾는 값이 없음
}

static int binSearch(int[] arr, int key) //for문으로 구현
{
    for(int startptr = 0, endptr = arr.length-1, midptr = (startptr + endptr) / 2; startptr <= endptr; midptr = (startptr + endptr) / 2)
    {
        if(arr[midptr] == key) return midptr; //발견 함
        else //발견 못함
        {
            if(key > arr[midptr]) startptr = midptr + 1; //키가 배열 뒷 쪽에 있음
            else endptr = midptr -1; //키가 배열 앞 쪽에 있음
        }
    }
    return -1; //찾는 값이 없음
 }

 

실행 예제

public static void main(String[] args) {
    int arr[] = {5,7,15,28,29,31,39,58,68,70,95};

    System.out.println("key의 인덱스는 " + binSearch(arr, 39) + " 입니다.(-1이 나왔다면 찾는값이 없는 것입니다.)");
}
/*
key의 인덱스는 6 입니다.(-1이 나왔다면 찾는값이 없는 것입니다.)
*/

 

자세한 검색 과정 출력 예제

 

위 사진처럼 이진 검색의 과정을 자세히 출력하는 프로그램을 작성

(단, 각 행의 맨 왼쪽에 현재 검색하고 있는 요소의 인덱스를 출력하고, 검색범위의 맨 앞 요소 위에 <, 맨 끝 요소 위에 >, 현재 검색하고 있는 중앙 요소 위에 *를 출력)

static int binSearch(int[] arr, int key) //for문으로 구현
{
    System.out.print("  |");
    for(int i = 0; i < 2; ++i)
    {
        for(int j = 0; j < arr.length; ++j) 
        {
            if(i == 0) System.out.printf("%3d", j);
            else
            {
                if(j == 0) System.out.print("--+");
                else System.out.print("----");
            }
        }

        System.out.println();
    }

    for(int startptr = 0, endptr = arr.length-1, midptr = (startptr + endptr) / 2; startptr <= endptr; midptr = (startptr + endptr) / 2)
    {
        if(arr[midptr] == key)
        {
            for(int i = 0; i < 2; ++i)
            {
                if(i == 0)
                {
                    System.out.print("  |");
                    for(int j = 0; j < arr.length; ++j)
                    {
                        if(j == midptr)
                        {
                            System.out.printf("%3c\n", '*');
                            break;
                        }
                        else System.out.printf("%3c", ' ');
                    }
                }
                if(i == 1)
                {
                    System.out.print(" " + midptr + "|");
                    for(int j = 0; j < arr.length; ++j) System.out.printf("%3d", arr[j]);
                    System.out.println();
                }
            }
            return midptr;
        }	
        else
        {
            if(key > arr[midptr])
            {
                for(int i = 0; i < 3; ++i)
                {
                    if(i == 0)
                    {
                        System.out.print("  |");
                        for(int j = 0; j < arr.length; ++j)
                        {
                            if(j == startptr) System.out.printf("%3c", '<');
                            else if(j == endptr)
                            {
                                System.out.printf("%3c\n", '>');
                                break;
                            }
                            else if(j == midptr) System.out.printf("%3c", '*');
                            else System.out.printf("%3c", ' ');
                        }
                    }
                    else if(i == 1)
                    {
                        System.out.print(" " + midptr + "|");
                        for(int j = 0; j < arr.length; ++j) System.out.printf("%3d", arr[j]);
                        System.out.println();
                    }
                    else System.out.println("  |");
                }
                startptr = midptr + 1;
            }
            else 
            {
                for(int i = 0; i < 3; ++i)
                {
                    if(i == 0)
                    {
                        System.out.print("  |");
                        for(int j = 0; j < arr.length; ++j)
                        {
                            if(j == startptr) System.out.printf("%3c", '<');
                            else if(j == endptr)
                            {
                                System.out.printf("%3c\n", '>');
                                break;
                            }
                            else if(j == midptr) System.out.printf("%3c", '*');
                            else System.out.printf("%3c", ' ');
                        }
                    }
                    else if(i == 1)
                    {
                        System.out.print(" " + midptr + "|");
                        for(int j = 0; j < arr.length; ++j) System.out.printf("%3d", arr[j]);
                        System.out.println();
                    }
                    else System.out.println("  |");
                }
                endptr = midptr -1;
            }

        }
    }
    return -1; //찾는 값이 없음
 }

 

실행 예제

public static void main(String[] args) {
    int arr[] = {5,7,15,28,29,31,39,58,68,70,95};
    System.out.println("key의 인덱스는 " + binSearch(arr, 58) + " 입니다.(-1이 나왔다면 찾는값이 없는 것입니다.)");
}
/*
  |  0  1  2  3  4  5  6  7  8  9 10
--+----------------------------------------
  |  <              *              >
 5|  5  7 15 28 29 31 39 58 68 70 95
  |
  |                    <     *     >
 8|  5  7 15 28 29 31 39 58 68 70 95
  |
  |                    <  >
 6|  5  7 15 28 29 31 39 58 68 70 95
  |
  |                       *
 7|  5  7 15 28 29 31 39 58 68 70 95
key의 인덱스는 7 입니다.(-1이 나왔다면 찾는값이 없는 것입니다.)
*/

 

맨 앞의 원소의 인덱스를 리턴하는 이진 검색

위에 작성된 이진검색 알고리즘은 검색할 값과 같은 값을 갖는 요소가 하나 이상일 경우 그 요소 중에서 맨 앞의 요소를 찾지 못한다.

예를 들어 {1,3,5,7,7,7,7,8,8,9,9} 이렇게 배열이 이뤄져 있고, 7을 찾고 싶다면 인덱스 5밖에 리턴을 하지 못하는데, 같은 원소의 맨 앞의 인덱스를 리턴하는 이진검색 알고리즘은 아래와 같다.

static int binSearchX(int[] arr, int key) //for문으로 구현
{
    for(int startptr = 0, endptr = arr.length-1, midptr = (startptr + endptr) / 2; startptr <= endptr; midptr = (startptr + endptr) / 2)
    {
        if(arr[midptr] == key) //키를 찾음
        {
            for(int i = midptr; i > 0; --i) //맨 앞의 키를 찾는 과정
            {
                if(i == 1 && arr[i-1] == key) return i-1;
                if(arr[i-1] == key) continue;
                    return i;
            }
        }
        else //발견 못함
        {
            if(key > arr[midptr]) startptr = midptr + 1; //키가 배열 뒷 쪽에 있음
            else endptr = midptr -1; //키가 배열 앞 쪽에 있음
        }
    }
    return -1; //찾는 값이 없음
 }

 

실행 예제

public static void main(String[] args) {
    int []arr = {1,3,5,7,7,7,7,8,8,9,9};
    System.out.println("key는 " + binSearchX(arr, 7) + "에 있습니다.");
}
/*
key는 3에 있습니다.
*/

 

Arrays.binarySearch API

자바는 배열에서 이진 검색을 하는 메소드를 표준 라이브러리로 제공한다.

이진 검색 표준 라이브러리의 메소드로는 java.util.Arrays 클래스의 binarySearch 메소드가 있다.

binarySearch 메소드는 다음과 같은 장점이 있다.

• 이진 검색 메소드를 직접 코딩할 필요가 없다.
• 모든 자료형 배열에서 검색을 할 수 있다.

binarySearch 메소드는 위와 같이 오버로딩되어 있다.

 

검색에 성공한 경우

key와 일치하는 요소의 인덱스를 리턴한다. 일치하는 요소가 여러 개 있다면 무작위의 인덱스를 리턴한다.

맨 앞의 인덱스나 어떤 특정한 인덱스를 리턴하는 것이 아님

 

검색에 실패한 경우

리턴 값은 삽입 포인트를 x라고 할 때 -x -1을 리턴한다.

위 배열에서 key가 4이면 삽입 포인트는 3이다. 즉, -4를 리턴한다.

삽입 포인트
삽입 포인트는 검색하기 위해 지정한 key보다 큰 요소 중 첫 번째 요소의 인덱스이다. 만약 배열의 모든 요소가 key보다 작다면 배열의 길이를 삽입 포인트로 정한다.

 

 

실행 예제

import java.util.Arrays;
public class Main2{
	public static void main(String[] args) {
		int []arr = {5,7,15,28,29,31,39,58,68,70};
		System.out.println("key는 " + Arrays.binarySearch(arr, 39) + "에 있습니다.");
		System.out.println("key는 " + Arrays.binarySearch(arr, 30) + "에 있습니다.");
		System.out.println("key는 " + Arrays.binarySearch(arr, 99) + "에 있습니다.");
	}
}
/*
key는 6에 있습니다.
key는 -6에 있습니다.
key는 -11에 있습니다.
*/