이진 탐색(Binary Search)

🟩 정렬된 리스트 형태로 주어진 원소들을 절반씩 줄여 가면서 원하는 값을 가진 원소를 찾는 방법

분할정복 방법이 적용됨

주어진 배열이 정렬되어 있지 않으면 정렬 수행

 

🟩 탐색 방법

배열의 가운데 원소 A[mid]와 탐색키 key를 비교

 

🌟 중간 값을 구하는 방식

1. mid : low + (high-low) / 2

2. mid : (low + high) / 2 👉 low + high 값이 (2^31-1)의 범위보다 크다면 음수값으로 오버플로우 발생 가능

 

1. A[mid] = key 👉 탐색 성공 (인덱스 mid 반환 후 종료)

2. A[mid] < key 👉 이진 탐색(원래 크기의 1/2인 오른쪽 부분배열) 순환 호출

3. A[mid] > key 👉 이진 탐색(원래 크기의 1/2인 왼쪽 부분배열) 순환 호출

 

👉 탐색을 반복할 때마다 대상 원소의 개수가 1/2씩 감소

 

🌟 반복문을 이용하는 방법

int BSearch(int arr[], int target) {
    int low = 0;
    int high = arr.length - 1;
    int mid;

    while(low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

 

🌟 재귀함수를 이용하는 방법

int BSearchRecursive(int arr[], int target, int low, int high) {
    if (low > high)
        return -1;

    int mid = (low + high) / 2;
    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return BSearchRecursive(arr, target, low, mid-1);
    else
        return BSearchRecursive(arr, target, mid+1, high);
}

 

🟩 시간 복잡도 O(logn)

탐색 : O(logn)

초기화 : O(nlogn)

삽입/삭제 : O(n)

 

🟩 활용

삽입과 삭제가 빈번한 경우에는 부적합

연산 후 리스트의 정렬 상태를 유지하기 위해서는 O(n)의 데이터 이동 필요 👉 데이터가 작은 경우 적합