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

이진 탐색(Binary Search)란?

• 이진 탐색이란 데이터가 반드시 정렬되어 있는 상태에서 특정한 값을 찾아내는 알고리즘입니다.

이진 탐색 동작 원리

• 정렬된 배열에서 x값을 찾고자 할 때

1. 정렬된 배열의 중간값과 x를 비교하고 일치한다면 해당 인덱스 값을 반환하고 일치하지 않다면 2번과정으로 넘어갑니다.
2. 중간값과 같으면 해당 값을 반환합니다.
3. 중간값보다 작으면 중간값의 왼쪽에 나열된 값들을 비교합니다. 중간값보다 크다면 중간값의 오른쪽에 나열된 값들을 비교합니다.
4. 2 ~ 3번 과정을 반복합니다.
5. 비교할 값이 더이상 없다면 -1을 반환합니다.

ex) {1, 5, 7, 13, 15, 23}으로 정렬된 배열이 있을 때 15라는 값을 찾고자 하는 경우

1. 인덱스가 0 ~ 5인 정렬된 배열이므로 중간값은 (0 + 5) / 2 = 2, 인덱스가 2인 값이 중간값이 되며 해당 값은 7입니다. 따라서 7과 비교할 값 15를 비교했을 때 7이 더 작으므로 배열에서 해당 값 보다 큰 오른쪽에 나열된 13, 15, 23과 비교하게 됩니다.
2. {13, 15, 23} 의 중간값을 구합니다. -> 15
   중간값과 비교할 값 15를 비교하였을 때 일치하므로 해당 인덱스 값을 반환하게 됩니다.

JAVA 코드

반복문(for)을 이용한 방법

int BinarySearch(int sortArr[], int target){  
    int min = 0; // // sortArr에서 최소 index값을 얻음  
    int max = sortArr.length -1; // sortArr에서 최대 index값을 얻음  
    int middle; // 정렬된 sortArr이라는 배열에서 중간 인덱스 값을 얻을 변수  

    // 최소 인덱스 값이 최대 인덱스 값보다 클 경우 중간 인덱스 값이 음수가 나오게 되므로 비교 불가  
    while(min <= max){  
     middle = (min + max) / 2;  

        if (sortArr[middle] == target){  
         return middle;  
        }else if(sortArr[middle] > target){ // 찾고자 하는 target 값보다 중간값이 큰 경우왼쪽 값들을 비교합니다.  
         max = middle - 1;  
        }else{  
         min = middle + 1;  
        }  
        return -1;  
    }  
}  

재귀함수를 이용한 방법

int BinarySearchRecursive(int sortArr[], int target, int min, int max){  
// 재귀함수를 종료할 시점을 나타내줍니다. 위 반복문 방법에서 while 조건문과 비교하시면 이해하기가 좀 더 쉽습니다.  
    if(min > max){  
     return -1;  
    }  

    int middle = (min + max) / 2; // sortArr의 중간 인덱스 값을 구합니다.  
    // 찾고자 하는 값을 정렬된 배열에서 찾았다면 해당 인덱스를 반환해주고 재귀함수를 종료합니다.  
    if (sortArr[middle] == target){  
     return middle;  
    }else if(sortArr[middle] > target){  
     return BinarySearchRecursive(sortArr, target, min, middle-1);  
    }else{  
     return BinarySearchRecursive(sortArr, target, middle+1, max);  
    }  
}  

이진 탐색(Binary Search) 시간 복잡도

• 이진 탐색(Binary Search)의 시간 복잡도는 O(logN) 입니다.
• 처음 N개 크기의 배열에서 단계가 하나씩 지날때마다 탐색할 배열의 크기가 절반씩 줄어들기 때문입니다. 비교할 크기가 N, N/2, N/4 ... 1으로 실행되므로 2^K = N, K = log2N 입니다.