close

C++의 이진 검색 (Binary Search) 알고리즘- 설명, 예제 및 코드

이진 검색 알고리즘은 정렬된 목록에서 특정 요소를 검색하는 보다 효율적인 방법입니다. 요소를 순차적으로 검사하는 선형 검색과 달리 이진 검색은 목록을 반으로 나누고 대상 요소와 중간 요소를 비교합니다. 이 과정은 대상 요소를 찾거나 검색 범위가 비워질 때까지 반복됩니다.

작동 방식

  1. 전체 정렬된 목록으로 시작합니다.
  2. 현재 검색 범위의 중간 요소를 찾습니다.
  3. 중간 요소를 대상 값과 비교하십시오.
  4. 중간 요소가 대상 값과 같으면 검색이 성공한 것입니다.
  5. 가운데 요소가 대상보다 큰 경우 범위의 왼쪽 절반에서 검색합니다.
  6. 중간 요소가 대상보다 작은 경우 범위의 오른쪽 절반에서 검색합니다.
  7. 대상 요소를 찾거나 검색 범위가 비워질 때까지 2-6단계를 반복합니다.

예

정렬된 정수 목록을 고려하고 이진 검색을 사용하여 숫자 34를 찾고자 합니다.

정렬된 목록: {12, 23, 34, 45, 56, 67, 89, 90}

  1. 전체 목록부터 시작하십시오.
  2. 중간 요소: 56(위치 4). 34와 비교하십시오.
  3. 56은 34보다 큽니다. 왼쪽 절반에서 검색합니다.
  4. 새로운 중간 요소: 23(위치 1). 34와 비교하십시오.
  5. 23은 34보다 작습니다. 오른쪽 절반에서 검색합니다.
  6. 새로운 중간 요소: 45(위치 3). 34와 비교하십시오.
  7. 45는 34보다 큽니다. 왼쪽 절반에서 검색합니다.
  8. 새로운 중간 요소: 34(위치 2). 대상을 찾았습니다.

C++의 예제 코드 

#include <iostream>  
#include <vector>  
  
int binarySearch(const std::vector<int>& arr, int target) {  
    int left = 0;  
    int right = arr.size()- 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;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 23, 34, 45, 56, 67, 89, 90};  
    int target = 34;  
  
    int result = binarySearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}

주어진 예에서 binarySearch 함수는 정렬된 정수 목록에서 숫자 34를 찾는 데 사용됩니다. 결과는 목록에서 34번째 위치(0부터 시작하는 위치) 또는 숫자를 찾을 수 없는 경우 -1이 됩니다.