이진 탐색

이진 탐색

범위를 반씩 좁혀가며 탐색하는 이진탐색

데이터를 확인할 일이 있을 때 그 데이터를 하나씩 확인하여 처리할 때 순차 탐색을 통해 확인하였습니다. 이렇게 순차적으로 확인하면 만약 데이터가 맨 끝에 있을 경우 있기에 순차 탐색의 시간복잡도는 O(N)이 입니다.

그에 반해 이진 탐색은 정렬되어 있지 않을 땐 사용할 수 없지만 데이터가 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있습니다. 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있습니다.

이진 탐색은 시작점, 끝점, 중간점 세 개의 변수를 사용하게 됩니다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾게 됩니다.

아래는 재귀 함수로 구현한 이진 탐색 소스코드입니다.

import java.util.Scanner;

public class Recursive {

    public static int binarySearch(int[] arr, int target, int start, int end) {
        if (start > end) {
            return -1;
        }

        int mid = (start + end) / 2;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int target = sc.nextInt();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int result = binarySearch(arr, target, 0, n - 1);
        if (result == -1) {
            System.out.println("찾는 원소가 배열에 존재하지 않습니다.");
        } else {
            System.out.println(result + 1);
        }
    }
}

• 이진 탐색 함수에 탐색할 배열, target 데이터, 시작점, 끝 점을 매개변수로 넘겨줍니다.
• 이진 탐색으로 배열을 모두 탐색했지만 target 데이터가 없을 경우 재귀를 빠져나오기 위해 start > end if 조건문을 사용합니다.
• mid 라는 정수타입 변수에 시작과 끝을 더한 값을 절반으로 나눠 변수에 넣어줍니다.
• 절반으로 나눈 그 위치에 target 데이터가 있다면 해당 위치를 return 해줍니다.
• 그렇지 않고 target 데이터보다 mid 위치에 있는 데이터의 값이 크다면 현재 arr는 정렬이 되어있다는 가정하에 이진탐색을 하기 때문에 target 데이터는 중간값보다 작다는 의미로 mid보다 작은 수가 있는 왼편으로 범위를 좁힙니다.
• 재귀로 자기 자신을 다시 호출하면서 이번엔 좁아진 범위로 인해 끝점을 mid - 1로 넘겨줍니다.
• 이런 반복된 작업으로 mid == target에 걸리게 되면 binarySearch 재귀 함수는 끝나게됩니다. (끝까지 걸리지 않는다면 첫번째 if 조건문에 걸려 -1 을 반환하게 될 것입니다)

이런 이진 탐색은 절반씩 범위를 좁히면 나머지 절반은 탐색할 이유가 없으므로 ```O(log N)```의 시간 복잡도를 갖게 됩니다. 찾고 싶은 데이터가 정렬되어 있다면 이진 탐색을 이용해 빠르게 찾는 방법이 좋은 것 같습니다.