[Algorithm] Binary Search (이분 탐색) 구현방법, 예시

[Algorithm] Binary Search (이분 탐색) 이란?

 

Binary Search(이분 탐색) 이란?

| 정렬된 배열에서 특정한 값을 찾는 검색 알고리즘 |

• `중간 지점`의 값을 확인하여 찾고자 하는 값과 비교
  • 만약 다르다면, 검색 범위를 1/2로 축소
• 배열이 미리 `정렬` 되어있어야 한다.

 

 

Binary Search - 장점

1. 선형 탐색(linear search)에 비해 매우 빠른 검색 시간 제공
2. 시간 복잡도는 `O(log n)` 이다.

 

Binary Search - 구현 방법

1. 배열의 가장 낮은 인덱스를 `low`로, 가장 높은 인덱스를 `high`로 설정합니다.
2. `low`가 `high`보다 작거나 같은 동안 반복합니다:
   • 중간 지점 `mid`를 (`low` + `high`) / 2로 계산합니다.
   • 중간 지점의 값이 찾고자 하는 값과 같다면, 위치를 반환합니다.
   • 중간 지점의 값이 찾고자 하는 값보다 크다면, `high`를 `mid` - 1로 업데이트합니다.
   • 중간 지점의 값이 찾고자 하는 값보다 작다면, `low`를 `mid` + 1로 업데이트합니다.
3. 찾고자 하는 값이 배열에 없다면, 검색을 종료합니다.

 

 

Binary Search 예시 (C++)

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector<int>& nums, int target) {
    int low = 0, high = nums.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2; // 오버플로우를 방지하기 위한 계산 방식
        if (nums[mid] == target) return mid; // 타겟을 찾은 경우
        else if (nums[mid] < target) low = mid + 1; // 타겟이 중간값보다 큰 경우
        else high = mid - 1; // 타겟이 중간값보다 작은 경우
    }
    return -1; // 타겟을 찾지 못한 경우
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int target = 4;
    int result = binarySearch(nums, target);
    if (result != -1) cout << "Element found at index " << result << endl;
    else cout << "Element not found in the array" << endl;
    return 0;
}

 

정렬된 배열 `nums` 에서 찾고자 하는 값 `target`을 탐색하고자 한다.

 

| 1. 배열의 가장 낮은 인덱스를 low 로, 가장 높은 인덱스를 high 로 설정 |

• `binarySearch` 함수에서 각각 변수로 설정한다.

| 2. low가 high 보다 작거나 같은 동안 반복합니다 |

• `while(low <= high)` 문 안에서 계속 반복한다.
  • 중간 지점 `mid`를 (`low` + `high`) / 2로 계산합니다.
  • 중간 지점의 값이 찾고자 하는 값과 같다면, 위치를 반환합니다.
  • 중간 지점의 값이 찾고자 하는 값보다 크다면, `high`를 `mid` - 1로 업데이트합니다.
  • 중간 지점의 값이 찾고자 하는 값보다 작다면, `low`를 `mid` + 1로 업데이트합니다.

| 3. 찾고자 하는 값이 배열에 없다면, 검색을 종료합니다. |

• "Element not found in the array" 를 출력한다.