(탐색알고리즘) 이진 탐색(Binary Search)

이진 탐색(Binary Search)

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다.

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있습니다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 됩니다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있습니다.

이진탐색을 설명하기 위해 한 가지의 예로 아래의 정렬된 데이터에서 22를 검색하는 과정을 설명하겠습니다.

5

11

13

19

22

38

42

첫 번째 과정으로 데이터 집합의 중앙을 선택합니다. 

low : 0

high : 7

mid : (low+high)/2 = 3

5 (low)

11

13

19 (mid)

22

38

42 (high)

두 번째 과정은 데이터의 순서가 오름차순으로 되어있기 때문에 왼쪽은 중앙요소보다 작고, 오른쪽은 큽니다. 검색하려는 데이터가 중앙값보다 크다면 오른편에서 중앙 요소를 다시 선택합니다. 그리고 다시 이진 탐색을 시작합니다.

low : (mid+1) = 4

high : 7

mid : (low+hight)/2 = 5

5

11

13

19

22 (low)

38(mid)

42 (high)

22는 38보다 작기 때문에 왼편에서 중앙 값을 선택합니다. 그러면 남은 데이터 22가 중앙값으로 선택되는데 찾으려는 데이터와 일치하기 때문에 검색을 끝마칩니다.

과정을 보면서 왜 이진탐색이라는 이름이 붙은 이유를 아시겠습니까?! 한번 비교를 거칠때 탐색 범위가 반으로 줄어들기 때문입니다. 

이진 탐색의 성능은 한번 이진탐색을 할 때마다 탐색 범위가 1/2로 되기 때문에 아래와 같은 수식이 만들어 집니다.

package search;

import java.util.Scanner;

public class BinarySearch {

    public static void main(String[] args) {
        int[] dataArray = { 5, 11, 13, 19, 22, 38, 42 };
        System.out.println("검색할 데이터를 입력하세요");
        Scanner scan = new Scanner(System.in);
        int search = Integer.parseInt(scan.nextLine().trim());

        int result = binarySearch(dataArray, search);
        if (result == -1)
            System.out.println("데이터를 찾지 못하였습니다");
        else
            System.out.println("데이터의 위치는 " + result + "번 째입니다.");

    }

    public static int binarySearch(int[] arr, int search) {
        int low = 0;
        int mid = 0;
        int high = arr.length;

        while (low <= high) {
            mid = (low + high) / 2;

            if (arr[mid] < search) {
                low = mid + 1;
            } else if (arr[mid] > search) {
                high = mid - 1;
            } else
                return mid;
        }
        return -1;
    }

}