[JAVA] 이분 탐색(Binary Search)

이분 탐색(Binary Search)이란?

• ‘정렬된 배열’에서 ‘특정 값’을 찾는 알고리즘을 의미합니다.
• 이진탐색은 탐색 범위를 절반씩 줄여나가기 때문에 선형탐색에 비해 빠른 속도를 보장합니다. 하지만 배열이 정렬되어 있어야 한다는 조건이 필요하기 때문에 배열이 정렬되어 있지 않은 경우에는 정렬 작업이 필요합니다.

1. 이진탐색 과정
   

1. 배열의 ‘중간 값’을 선택하여 찾고자 하는 값과 비교합니다.
2. 만약 중간 값이 찾고자 하는 값보다 크면 ‘배열 왼쪽 부분'에서 탐색을 진행하고, 값보다 작으면 ‘배열 오른쪽 부분'에서 탐색을 진행합니다.
3. 이 과정에서 찾고자 하는 값이 나올 때까지 반복합니다.

Start = 0
End = 배열의 길이 -1
Mid = (Strat + End) / 2

 

또한, 대표적으로 3가지 아이디어를 기억하시면 됩니다. (오름차순 기준)

1) 찾고자 하는 값이 배열[Mid]의 값보다 큰 경우, Start 값을 증가시킵니다.
Start = Mid + 1
2) 찾고자 하는 값이 배열[Mid]의 값보다 작은 경우, End 값을 감소시킵니다.
End = Mid - 1
3) 찾고자 하는 값이 배열[Mid]에 위치한 경우, Mid를 반환합니다.
return Mid

 

이분 탐색 구현(Java)

반복문으로 구현

    public static boolean BSearch(int[] arr, int n) {
        int left = 0;
        int right = arr.length - 1;
        int mid;

        while (left <= right) {
            mid = (left + right) / 2;
            if (arr[mid] < n) left = mid + 1;
            else if (arr[mid] > n) right = mid - 1;
            else return true;
        }
        return false;
    }

 

재귀로 구현

    public static boolean BSearchRecursive(int[] arr, int n, int left, int right) {
        if(left > right) return false;

        int mid = (left + right) / 2;

        if (arr[mid] < n) 
            return BSearchRecursive(arr, n, mid +1, right);
        else if (arr[mid] > n) 
            return BSearchRecursive(arr, n, left, mid - 1);
        else 
            return true;

    }