[Algorithm] 자바 이진 탐색 (Binary Search) / 이분 탐색 -Gyunny

이진 탐색 (Binary Search)

이진 탐색은 이분 탐색, Binary Search라고도 부릅니다. 그리고 이진 탐색은 순차적 탐색보다 빠른 탐색을 하기 위해 고안된 탐색 알고리즘으로 실제로 이분 탐색의 시간 복잡도가 순차적 탐색의 시간 복잡도보다 낮습니다.

즉, 이진 탐색은 정렬된 배열 또는 리스트에서 특정 값을 찾는 적합한 고속 탐색 알고리즘입니다.
배열이 정렬되어 있어야 한다는 조건이 필요하기 때문에 배열이 정렬되어 있지 않은 경우에는 정렬 작업이 필요합니다.

순차적 탐색

• 정렬된 배열 안에서 특정 원소를 찾기 위해 인덱스가 0인 원소부터 차례대로 탐색합니다.
• 순차적으로 탐색하기 때문에 원소를 중간에 건너뛰지 않습니다.

이분 탐색

• 정렬된 배열 안에서 특정 원소를 찾을 때 인덱스 i부터 j의 중간값과 비교합니다.
• 중간값이 찾는 원소가 아니라면 인덱스 i와 j를 다시 정해줍니다.
• 인덱스 i와 j를 정할 때 마다 탐색 범위가 반으로 줄어듭니다.

이진 탐색 방법

• 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내 탐색의 범위를 반으로 줄일 수 있습니다.
• 찾고자 하는 값이 속해있지 않은 부분은 전혀 고려할 필요가 없기 때문에, 매 단계에서 검색해야 할 리스크의 크기를 반으로 줄일 수 있습니다.
• 이러한 방법을 반복적으로 사용해 탐색하는 방법이 이진 탐색입니다.
• 데이터 삽입이나 삭제가 빈번할 시 적합하지 않고, 주로 고정된 데이터에 대한 탐색에 적합합니다.

구현

1. 탐색의 대상이 되는 자료들이 array[left] 에서부터 array[right]에 있다고 가정 (정렬된 상태)
   1. 즉, 어떤 시점에서 탐색되어야 할 범위는 left 에서 right 까지가 됩니다.
   2. 맨 처음 left 에는 0 인덱스 값, right 에는 n - 1 인덱스의 값이 들어갑니다.
2. left 와 high right 의거해 중간값 mid 값은 ( left  + right ) / 2 입니다.
   1. 즉, array[ left  ] ~ array[ left  ]까지의 탐색은 array[ left  ] ~ array[middle - 1] + array[middle + 1] + array[ right  ]까지의 탐색이 됩니다.
3. array[mid] 값과 구하고자 하는 key 값을 비교합니다.
   1. key > mid : 구하고자 하는 값이 중간 값보다 높다면 low를 mid + 1로 만들어줍니다. (왼쪽 반을 버립니다.)
   2. key < mid : 고하고자 하는 값이 중간 값보다 작다면 high를 mid - 1로 만들어줍니다. (오른쪽 반을 버립니다.)
   3. key === mid : 고하고자 하는 값을 찾았으므로 중간값을 리턴해줍니다.
4. left  > right 가 될 때까지 1~3번 반복하며 구하고자 하는 값을 찾습니다.
   1. 못찾으면  탐색 실패로 -1, false, error 등을 return해 줍니다.

재귀를 이용한 이진 탐색 구현

public static int binarySearch(int[] arr, int n, int left, int right) {
    int mid = (left + right) / 2;
    
    if (left <= right) {
        if (arr[mid] == n) { // 탐색 성공
            return mid;
        } else if (arr[mid] > n) {
            // 왼쪽 부분 arr[0] 부터 arr[mid-1]에서의 탐색
            return binarySearch(arr, n, left, mid - 1);
        } else {
            // 오른쪽 부분 -arr[mid+1] 부터 arr[high]에서의 탐색
            return binarySearch(arr, n, mid + 1, right);
        }
    }
    
    return -1; // 탐색 실패
}

반복을 이용한 이진 탐색 구현

public static int binarySearch2(int[] arr, int n) {
    int left = 0;
    int right = arr.length - 1;
    int mid;
    
    while (left <= right) {
        mid = (low + high) / 2;
        
        if (arr[mid] == n) {
            return mid;
        } else if (key < arr[mid]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

이진 탐색의 시간 복잡도

이진 탐색은 탐색을 반복할 때마다 탐색 범위를 반으로 줄입니다. → O(log n)