23.07.13 스터디 정리
데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘입니다.
대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는 것입니다.

Binary Search 이진탐색

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘입니다.
대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는 것입니다.

다시말해, 이진 탐색은 이분법이라는 접근 방식을 사용하여 값을 찾으며, 시간 복잡도는 O(log N)입니다.
이진 탐색의 원리와 시간 복잡도를 이해하면 정렬된에서 원하는 값을 빠르게 찾는 데 도움이 됩니다.

이진 탐색의 수행 절차

1. 배열의 중간 값과 찾고자 하는 값의 크기를 비교합니다.
2. 찾고자 하는 값이 배열의 중간 값보다 크다면 오른쪽 또는 작다면 왼쪽 하위 배열에서 계속해서 중간 값을 확인합니다.
3. 목표 값과 일치하는 원소를 찾거나 검색 범위가 없을 때까지 1~2 과정을 반복합니다.

이진 탐색의 시간 복잡도

이진 탐색는 각 단계마다 탐색 범위가 절반이 되기 때문에
최대 N번의 값을 확인한 후, 검색 범위가 1이 될 때까지의 횟수를 복잡성이라고 할 수 있습니다.

즉, log2(N)을 사용하면 이진 탐색에서 몇 번만에 다음을 찾을 수 있는지 알 수 있습니다.
따라서 이진 탐색의 시간 복잡도는 O(log N)입니다.

또한, 이진 탐색의 성능은 데이터의 크기나 정렬된 정도와 관계없이 이루어집니다.
따라서 값이 큰 정렬된 데이터에 효과적으로 사용할 수 있습니다.

핵심이론

이진 탐색은 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복합니다.

이진 탐색 과정 (다시 설명)

1. 현재 데이터셋의 중앙값을 선택합니다.
2. 중앙값 > 타깃 데이터일 때, 중앙값 기준으로 왼쪽 데이터셋을 선택합니다.
3. 중앙값 < 타깃 데이터 일 때, 중앙값 기준으로 오른쪽 데이터셋을 선택합니다.
4. 과정 1~3을 반복하다가 타깃 == 중앙값 데이터일 때 탐색을 종료합니다.

CODE

정렬된 배열에서 특정 값을 찾는 이진 탐색 함수

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // 타겟이 배열에 없는 경우 -1 반환
    }

    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}; // 예시 정렬된 배열
        int target = 14;
        int result = binarySearch(arr, target);

        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

코드 설명

binarySearch 함수는 정렬된 배열 arr에서 목표 값 target을 찾는 이진 탐색 알고리즘을 구현합니다.
올바른 인덱스를 찾으면 바로 반환하고, 목표 값을 찾지 못하면 -1을 반환합니다. main 함수에서는 정렬된 배열과 목표 값을 지정한 다음, 이진 탐색 함수를 호출하여 결과를 출력하게 됩니다.