이진 탐색(Binary Search)

이진탐색을 알기전에 먼저 순차탐색을 알아야한다. 순차탐색(Sequential Search)는 배열 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 보통 정렬되지 않은 배열에서 데이터를 찾아야 할 때 사용한다. 배열에서 원소의 개수를 확인하는 count() 메서드를 이용할때도 내부에서는 순차 탐색이 수행된다.

 

이진탐색

이진 탐색(Binary Search)는 반으로 쪼개면서 탐색하는 방법 으로 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위일때는 사용할 수 없지만 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있는 특징이 있다.

이진탐색은 위치를 나타내는 변수 시작점, 끝점, 중간점을 사용한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해 원하는 데이터를 찾는 게 이진 탐색과정이다.

 

 

정렬된 7개의 데이터중 6을 찾아야 하는 예시가 존재한다.

1. 시작점 9, 끝점 1, 그리고 중간점으로 4로 정하고 찾아야하는 값 6과 중간점 4을 비교한다.
2. 6> 4 이므로 4보다 작은 값은 다 제외한다.
3. 다시 [9 7 6] 3개의 값중에서 시작점 9 , 끝점 6 그리고 중간점 7로 정한다.
4. 7 > 6이므로 7보다 큰값은 다 제외한다.
5. 6과 6이 동일하므로 탐색 종료

이진탐색을 구현하는 방법에는 2가지가 있는데 한가지는 재귀 함수를 이용, 한가지는 단순하게 반복문을 이용하는 방법이다.

Java Code

• 재귀함수를 사용해 이진탐색 구현

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {0, 1, 2, 3, 4, 5, 6, 7};//정렬되어 있어야함.
        int target = 2;

        BinarySearch(arr, 0, arr.length - 1, target);
        System.out.print("Sorted Array :" + Arrays.toString(arr));
    }


    public static int BinarySearch(int[] arr, int start, int end, int target) {
        if (start <= end) {

            int mid = (start + end) / 2; //중간값 idx, 소수점 이하는 버림

            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) { //target보다 중간값이 크면 중간값보다 큰 값은 제외
                BinarySearch(arr, start, mid - 1, target);

            } else if (arr[mid] > target) { //target보다 중간값이 작으면 중간값보다 작은 값은 제외
                BinarySearch(arr, mid - 1, 0, target);
            }
        }
        return -1; //탐색실패
    }
}

• 단순 반복문을 사용해 이진탐색 구현

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {0, 1, 2, 3, 4, 5, 6, 7};//정렬되어 있어야함.
        int target = 2;

        BinarySearch(arr, 0, arr.length - 1, target);
        System.out.print("Sorted Array :" + Arrays.toString(arr));
    }

    static int BinarySearch(int[] arr, int start, int end, int target) {
        while (start <= end) {
            int mid = (start + end) / 2; //mid값 돌때마다 갱신

            if (mid == target) {
                return mid;
            } else if (target > arr[mid]) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return -1;//탐색실패
    }
}

이진탐색의 시간복잡도

운이좋으면 찾고자 하는 값이 중간값과 동일해 탐색이 끝나지만, 최악의 경우 데이터가 하나남을 때까지 탐색을 반복한다.

데이터의 개수가 N개 라고 했을 때,

• 첫번째 탐색 : N * 1/2
• 두번째 탐색 : 1/2 * N/2
• 세번째 탐색 : 1/2 * 1/2 * N/2

로 매 탐색마다 자료의 개수가 반씩 줄어든다. 따라서 k번 시행 후에는 (1/2)^K N 개가 남게되고, 탐색이 끝나는 시점에는 남은 자료가 1개가 되므로 (1/2)^K N = 1이 된다. 따라서 이때 양번에 2^K를 곱해주면 logN = k가 되므로 데이터 개수 N에 따른 시행횟수는 logN으로 따라서 시간복잡도 O(logN) 이 된다.

이진탐색의 공간복잡도

주어진 배열 안에서 교환을 하므로 O(N)이다.

이진탐색 특징

1. 검색이 반복될때마다 검색범위가 줄어들어 속도가 빠르다.
2. 배열 내부 데이터가 정렬되어 있어야한다.

 

 

참고 및 출처 

- https://jwoop.tistory.com/9