정렬된 배열에서 첫 번째 발생 위치 찾기

소개

이 랩에서는 C++ 에서 수정된 이진 탐색 (binary search) 을 사용하여 정렬된 배열에서 주어진 숫자가 처음 나타나는 위치를 찾는 방법을 배우겠습니다.

C++ 코드 파일

먼저, touch 텍스트 편집기를 사용하여 ~/project 디렉토리에 main.cpp라는 C++ 코드 파일을 생성해 보겠습니다.

touch ~/project/main.cpp

코드에 필요한 헤더 포함

프로그램에 필요한 C++ 헤더 파일을 포함해야 합니다. 다음 코드를 복사하여 main.cpp 파일에 붙여넣으세요.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

요소의 첫 번째 발생 위치를 찾는 함수 생성

배열, 하위 인덱스, 상위 인덱스 및 검색할 요소를 입력으로 받는 first()라는 함수를 생성합니다. 이 함수는 요소의 첫 번째 발생 위치의 인덱스를 반환합니다. 다음 코드를 main.cpp 파일에 포함하세요.

int first(int a[], int l, int h, int b)
{
    int res = -1;
    while (l <= h)
    {
        int m = (l + h) / 2;
        if (a[m] == b)
        {
            res = m;
            h = m - 1;
        }
        else if (a[m] > b)
        {
            h = m - 1;
        }
        else
        {
            l = m + 1;
        }
    }
    return res;
}

여기서는 이진 검색 (binary search) 을 사용하여 요소의 첫 번째 발생 위치를 찾았습니다. 요소가 배열에 없는 경우를 처리하기 위해 res 변수를 -1로 초기화했습니다. 중간 요소가 우리가 검색하는 요소와 같으면, 중간 요소의 인덱스를 res에 저장하고, 요소의 첫 번째 발생 위치를 찾고 있으므로 상위 인덱스를 m-1로 업데이트합니다. 중간 요소가 우리가 검색하는 요소보다 크면 상위 인덱스를 m-1로 업데이트하고, 작으면 하위 인덱스를 m+1로 업데이트합니다.

메인 함수 구현

main 함수에서 배열을 생성하고, 3 단계에서 생성한 first 함수를 적절한 인수로 호출하여 결과를 콘솔에 출력합니다. 아래 코드를 main 함수에 복사하여 붙여넣으세요.

int main()
{
    int a[] = {2, 3, 3, 4, 4, 4, 4, 4, 5};

    int n = sizeof(a) / sizeof(a[0]);

    int k = 4; //the element to find the first occurrence index of

    int f = first(a, 0, n - 1, k);

    if(f==-1)
    {
        cout << "Element not found\n";
    }
    else
    {
        cout << "The index of the first occurrence of " << k << " is: " << f << endl;
    }

    return 0;
}

여기서는 a라는 정수 배열을 선언하고 정렬된 정수 값으로 초기화했습니다. 또한 sizeof 연산자를 사용하여 배열의 요소 수를 계산했습니다. 그런 다음 적절한 인수로 first() 함수를 호출하고 결과를 출력했습니다.

C++ 코드 컴파일 및 실행

이제 다음 명령을 사용하여 C++ 코드를 컴파일하고 실행할 수 있습니다.

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

모든 것이 잘 진행되면 출력은 The index of the first occurrence of 4 is: 3이 됩니다.

요약

이 랩에서는 C++ 에서 수정된 이진 탐색 (binary search) 을 사용하여 정렬된 배열에서 주어진 숫자의 첫 번째 발생 위치를 찾는 방법을 배웠습니다. 알고리즘을 구현하기 위해 first() 함수를 생성했습니다.