Algo LowerBound

언리얼의 Algo로 이진 검색 하는 방법에 대해서 알아본다.

나중에 예제에 사용될 구조체이다.

//헤더 파일
USTRUCT(BlueprintType)
struct FMyStruct
{
    GENERATED_BODY()
public:
    FMyStruct();
    ~FMyStruct();
    UPROPERTY()
    FString Name;
    UPROPERTY()
    int id = 0;
};

//CPP 파일
FMyStruct::FMyStruct()
{
    //UE_LOG(LogTemp, Warning, TEXT("%p, %s (%d)"), this, *FString(__FUNCTION__), __LINE__);
}

FMyStruct::~FMyStruct()
{
    //UE_LOG(LogTemp, Warning, TEXT("%p, %s (%d)"), this, *FString(__FUNCTION__), __LINE__);
}

이진 검색으로 인덱스 찾기

Algo::BinarySearch는 오름차순일때 이진 검색으로 찾으면 인덱스를 반환한다.

    TArray<int> IntList;
    for (int n = 0; n < 10; n++)
        IntList.Add(n * 10);

    int Index = Algo::BinarySearch(IntList, 0); //결과 0
    int Index1 = Algo::BinarySearch(IntList, 10); //결과 1
    int Index2 = Algo::BinarySearch(IntList, 80); //결과 8

구조체를 이진 검색으로 인덱스 찾기

    TArray<FMyStruct> MyList;
    FMyStruct mySt;

    for (int n = 0; n < 10; ++n)
    {
        mySt.id = n;
        mySt.Name = FString::FromInt(n * 100);
        MyList.Add(mySt);
    }

    int MyListIndex3 = Algo::BinarySearchBy(MyList, 3, &FMyStruct::id); //결과 3
    int MyListIndex6 = Algo::BinarySearchBy(MyList, 6, &FMyStruct::id); //결과 6
    int MyListIndex9 = Algo::BinarySearchBy(MyList, 9, &FMyStruct::id); //결과 9
    int MyListIndex20 = Algo::BinarySearchBy(MyList, 20, &FMyStruct::id); //결과 -1

연산자 재정의를 하지 않아도 잘 찾는다.
다음과 같이 구조체의 연산자 재정의를 하여도 실행이 안된다.
언리얼이라 그런가 방법을 모르겠다.

    bool operator==(const FMyStruct& input)
    {
        return (id == input.id);
    }

    FMyStruct& operator=(const FMyStruct& input)
    {
        id = input.id;
        Name = input.Name;
        return *this;
    }

해당 값이 어느 인덱스 사이에 있는지 검색

배열에 추가하지 않고 어느 인덱스가 될지 알수 있다.
아래 LoweBound는 찾고자 하는 인덱스가 어느 인덱스 사이에 있는지 검색한다.
3번째 인자가 없으면 오름차순에서 TLess로 검색한다.

    TArray<int> IntList;
    for (int n = 0; n < 10; n++)
        IntList.Add(n * 10);

    int Lindex = Algo::LowerBound(IntList, 5); //Result 1
    int Lindex2 = Algo::LowerBound(IntList, 85); //Result 9
    int Lindex3 = Algo::LowerBound(IntList, -1); //Result 0
    int Lindex4 = Algo::LowerBound(IntList, 100); //Result 10

    //배열에 추가하지 않고 오름차순 순위를 구한다. 순위를 할려면 +1을 더한다.
    TArray<int> IntIncList;
    for (int n = 0; n < 10; ++n)
        IntIncList.Add(n * 10);

    int IncLindex = Algo::LowerBound(IntIncList, 100, TLess<int>()); //10
    int IncLindex1 = Algo::LowerBound(IntIncList, -100, TLess<int>()); //0
    int IncLindex2 = Algo::LowerBound(IntIncList, 85); //9
    int IncLindex3 = Algo::LowerBound(IntIncList, 90); //9
    int IncLindex4 = Algo::LowerBound(IntIncList, 90); //9

내림차순으로 어느 인덱스 사이에 있는지 검색

내림차순으로 정렬 되어 있을 때는 다음과 같이 람다 함수를 만들거나 TGreater<int>() 함수를 이용해 검색한다.

    TArray<int> IntList;
    for (int n = 9; n >= 0; --n)
        IntList.Add(n * 10);

    auto IntGreater = [](int A, int B)
    {
        return A > B;
    };

    int Lindex = Algo::LowerBound(IntList, 100, TGreater<int>()); //0

    int Lindex1 = Algo::LowerBound(IntList, -100, TGreater<int>()); //10
    int Lindex2 = Algo::LowerBound(IntList, 85, TGreater<int>()); //1
    int Lindex3 = Algo::LowerBound(IntList, 90, IntGreater); //0
    int Lindex4 = Algo::LowerBound(IntList, 25, IntGreater); //7
    int Lindex5 = Algo::LowerBound(IntList, 20, IntGreater); //7
    int Lindex6 = Algo::LowerBound(IntList, 90, IntGreater); //9

구조체로 어느 인덱스 사이에 있는지 검색

구조체로 검색할때는 아래와 같이 작성한다.

    TArray<FMyStruct> TestList;
    for (int k = 0; k < 10; ++k)
    {
        FMyStruct Item;
        Item.id = k * 10;
        Item.Name = FString::FromInt(Item.id) + TEXT("AAA");
        TestList.Add(Item);
    }

    auto MyStructLess = [](const FMyStruct& A, int B)
    {
        return A.id < B;
    };

    int StLindex = Algo::LowerBound(TestList, 100, MyStructLess); //10
    int StLindex1 = Algo::LowerBound(TestList, -100, MyStructLess); //0
    int StLindex2 = Algo::LowerBound(TestList, 85, MyStructLess); //9
    int StLindex3 = Algo::LowerBound(TestList, 90, MyStructLess); //9
    int StLindex4 = Algo::LowerBound(TestList, 90, MyStructLess); //9