List BinarySearch

C# List, 배열은 BinarySearch를 지원한다.
BinarySearch를 하기전에 정렬이 되어 있어야 한다.

using System;
using System.Collections.Generic;

class Test
{
    public void Run()
    {
        List<string> l = new List<string>();
        l.Add("acorn");      // 0
        l.Add("apple");      // 1
        l.Add("banana");     // 2
        l.Add("cantaloupe"); // 3
        l.Add("lettuce");    // 4
        l.Add("onion");      // 5
        l.Add("peach");      // 6
        l.Add("pepper");     // 7
        l.Add("squash");     // 8
        l.Add("tangerine");  // 9

        int i = l.BinarySearch("peach");
        Console.WriteLine(i);

        i = l.BinarySearch("banana");
        Console.WriteLine(i);

        i = l.BinarySearch("apple");
        Console.WriteLine(i);

        i = l.BinarySearch("abstract");
        Console.WriteLine(i + " complement ==> " + ~i);

        i = l.BinarySearch("assume");
        Console.WriteLine( i + " complement ==> " + ~i);
    }
}

실행 결과)
6
2
1
-1 complement ==> 0
-3 complement ==> 2

검색 결과가 0보다 작으면 값이 존재하지 않을때이다. "~" 보수로 바꾸면 결과값이 들어가야 할 위치이다.
"abstract"의 결과값은 -1 보수는 0이다.
"assume"의 결과값은 -3 보수는 2이다.

IComparer를 이용하여 커스텀 비교 함수를 만들수도 있다.
아래는 Start와 End값에 포함되는 인덱스를 찾는 예제이다.

주의사항)
List.BinarySearch를 실행 했을 때 Compare(lhs, rhs )로 넘어오는 값이 모노 C#과 윈도우즈 C#이 다르다.

BinarySearch Item 비교값이 Compare( ) 함수로 넘어올때 유니티 C#에서는 LHS, MS 윈도우즈 C#에서는 RHS이다.
유니티 C#에서는 this.End가 -1이다.
MS 윈도우즈 C#에서는 other.End가 -1이다.

플랫폼에 따라 범위 안에 포함되는지 체크를 달리 해야 한다.
BinarySearch에서 넘겨주는 item의( Range )의 End 값이 -1을 비교값으로 정한다.

using System;
using System.Collections.Generic;

public class Range
{
    public int Start { get; set; }
    public int End { get; set; }

    public Range( int start, int end)
    {
        Start = start;
        End = end;
    }

    public int Comp(Range other)
    {
        //BinarySearch Item 비교값이 Compare( ) 함수로 넘어올때
        //유니티 C#에서는 LHS, MS 윈도우즈 C#에서는 RHS이다.
        if (other.End == -1)
        {           
            int v = other.Start;
            if (v >= Start && v <= End)
                return 0;
        }
        else
        {
            int v = Start;
            if (v >= other.Start && v <= other.End)
                return 0;
        }

        int val = other.Start;
        if (Start > val)
            return 1;
        else if (Start < val)
            return -1;
        else
            return 0;
    }
}

public class RangeComparer : IComparer<Range>
{
    public int Compare(Range x, Range y)
    {
        return x.Comp(y);
    }
}

class Test
{
    public void Run()
    {
        List<Range> list = new List<Range>();
        list.Add(new Range(1, 10));
        list.Add(new Range(20, 100));
        list.Add(new Range(300, 1000));
        list.Add(new Range(4000, 10000));
        list.Add(new Range(50000, 60000));

        RangeComparer rangeComparer = new RangeComparer();
        int index = list.BinarySearch(0, 5, new Range(10, -1), rangeComparer);
        Console.WriteLine(index);
        index = list.BinarySearch(new Range(21, -1), rangeComparer);
        Console.WriteLine(index);
        index = list.BinarySearch(new Range(301, -1), rangeComparer);
        Console.WriteLine(index);
        index = list.BinarySearch(new Range(10000, -1), rangeComparer);
        Console.WriteLine(index);
        index = list.BinarySearch(new Range(50001, -1), rangeComparer);
        Console.WriteLine(index);
        
    }
}

실행결과)
0
1
2
3
4

참조)
https://www.dotnetperls.com/binarysearch