이진 탐색(Binary Search)

이진 탐색은 순차 탐색보다 대부분의 경우에서 더 빠른 효율을 낼 수 있다.

(찾으려는 값이 작으면, 순차 탐색이 더 적게 걸릴 수도 있다.)

 

순차 탐색은 보통 반복문을 이용하기 때문에, 시간복잡도 Big-O 기준 O(N)이다.

이진 탐색은 재귀를 통해 범위를 점점 좁혀나가는 방법으로, O(logN)이다.

 

다음 그림을 통해 이진 탐색에 대해 쉽게 파악할 수 있다.

 

https://blog.penjee.com/

 

 

다음은 이진 탐색을 구현하는 문제를 풀이한 코드들이다.

배열에서 num 값의 인덱스를 추출하는 문제이다.

 

1. while문 이용

import java.util.Arrays;
import java.util.Scanner;

class Main {
    private int solution(int target, int[] arr) {
        int answer = 0;
        int lt = 0, rt = arr.length - 1;

        Arrays.sort(arr);

        while (lt <= rt) {
            int mid = (lt + rt) / 2;

            if (arr[mid] == target) {
                answer = mid + 1;
                break;
            } else if (arr[mid] > target) {
                rt = mid - 1;
            } else {
                lt = mid + 1;
            }
        }

        return answer;
    }
}

 

2. 재귀 함수 이용

import java.util.Arrays;
import java.util.Scanner;

class Main {
    private int solution(int target, int[] arr, int left, int right) {
        if (left > right) {
            return -1;
        }

        int mid = (left + right) / 2;

        Arrays.sort(arr);

        if (arr[mid] > target)
            return solution(target, arr, left, mid - 1);
        else if (arr[mid] < target)
            return solution(target, arr, mid + 1, right);
        else
            return mid + 1;
    }
}

 

보통 기본적인 이진 탐색 문제들은 오름차순 정렬을 전제로 진행된다.

(심화적인 문제들은 정렬이 전제조건이 아닐 수 있음)

 

 

 

+ 부분 정렬된 이진 탐색 문제

ex) [4, 5, 6, 0, 1, 2, 3]

 

 

 

 

틀린 부분이 있다면, 댓글 달아주세요. 피드백 환영합니다.