C++ 동적 배열을 사용한 이진 탐색

소개

이진 탐색은 정렬된 배열에서 요소의 인덱스 위치를 찾는 탐색 방법입니다. C++ 에서는 반복적 (iterative) 및 재귀적 (recursive) 두 가지 접근 방식을 사용하여 이진 탐색을 수행할 수 있습니다. 이 랩에서는 동적 배열을 사용하여 이진 탐색 연산을 수행합니다.

새 C++ 파일 생성

먼저, ~/project 디렉토리에 main.cpp라는 이름의 새로운 C++ 파일을 생성합니다.

touch ~/project/main.cpp

헤더 파일 포함

다음으로, 필요한 헤더 파일인 iostream, algorithm, 그리고 vector를 포함합니다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

동적 배열 생성 및 요소 채우기

vector 클래스를 사용하여 정수형 동적 배열을 생성하고 정렬된 정수로 채웁니다.

vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};

이진 탐색 함수 구현

다음으로, 반복적인 접근 방식을 사용하여 정렬된 배열에서 요소의 인덱스 위치를 검색하는 이진 탐색 함수를 구현합니다.

int binarySearch(vector<int> arr, int target) {
    int low = 0;
    int high = arr.size() - 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 target = 7;
int result = binarySearch(arr, target);

if (result == -1) {
    cout << "Element not found!" << endl;
} else {
    cout << "Element found at index " << result << endl;
}

프로그램 컴파일 및 실행

다음 명령을 실행하여 터미널에서 프로그램을 컴파일하고 실행합니다.

g++ main.cpp -o main && ./main

최종 코드

다음은 main.cpp 파일의 전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int binarySearch(vector<int> arr, int target) {
    int low = 0;
    int high = arr.size() - 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 main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
    int target = 7;
    int result = binarySearch(arr, target);

    if (result == -1) {
        cout << "Element not found!" << endl;
    } else {
        cout << "Element found at index " << result << endl;
    }

    return 0;
}

요약

이 랩에서는 C++ 에서 동적 배열을 사용하여 이진 검색을 수행하는 방법을 배웠습니다. 반복적 접근 방식을 사용하고 정렬된 배열에서 요소의 인덱스 위치를 검색하는 이진 검색 함수를 구현했습니다. 또한 C++ 에서 vector 클래스를 사용하여 동적 배열을 만드는 방법도 배웠습니다.