C-Sharp/Algorithms.Tests/Search/FastSearcherTests.cs at 7f9aab2e139674fb7a62d0790faeb19f3e32e3d8 · TheAlgorithms/C-Sharp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
using Algorithms.Search;
using Utilities.Exceptions;

namespace Algorithms.Tests.Search;

public static class FastSearcherTests
{
    [Test]
    public static void FindIndex_ItemPresent_IndexCorrect()
    {
        // Arrange
        var searcher = new FastSearcher();
        var arr = Helper.GetSortedArray(1000);
        var present = Helper.GetItemIn(arr);

        // Act
        var index = searcher.FindIndex(arr, present);

        // Assert
        arr[index].Should().Be(present);
    }

    [TestCase(new[] { 1, 2 }, 1)]
    [TestCase(new[] { 1, 2 }, 2)]
    [TestCase(new[] { 1, 2, 3, 3, 3 }, 2)]
    public static void FindIndex_ItemPresentInSpecificCase_IndexCorrect(int[] arr, int present)
    {
        // Arrange
        var searcher = new FastSearcher();

        // Act
        var index = searcher.FindIndex(arr, present);

        // Assert
        arr[index].Should().Be(present);
    }

    [TestCase(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, 3)] // Item in left segment (< indexBinary)
    [TestCase(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, 5)] // Item at binary index
    [TestCase(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, 8)] // Item in right segment (> indexBinary)
    [TestCase(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, 1)] // Item at start
    [TestCase(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, 10)] // Item at end
    [TestCase(new[] { 1, 10, 20, 30, 40, 50, 60, 70, 80, 90 }, 20)] // Non-uniform distribution, interpolation < binary
    [TestCase(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 100 }, 100)] // Non-uniform distribution, interpolation > binary
    [TestCase(new[] { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 }, 50)] // Uniform spacing
    [TestCase(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }, 7)] // Larger array
    [TestCase(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }, 15)] // Larger array, right side
    public static void FindIndex_ItemPresentDeterministic_IndexCorrect(int[] arr, int present)
    {
        // Arrange
        var searcher = new FastSearcher();

        // Act
        var index = searcher.FindIndex(arr, present);

        // Assert
        arr[index].Should().Be(present);
    }

    [Test]
    public static void FindIndex_ItemPresentInArrayOfDuplicates_IndexCorrect()
    {
        // Arrange
        var searcher = new FastSearcher();
        var arr = CreateArrayOfDuplicates(1000, 0); // Helper for large duplicate arrays
        var present = 0;

        // Act
        var index = searcher.FindIndex(arr, present);

        // Assert
        arr[index].Should().Be(0);
    }

    [TestCase(new int[0], 2)] // Empty array
    [TestCase(new[] { 1, 2, 3 }, 4)] // Item missing in array
    public static void FindIndex_ItemMissing_ItemNotFoundExceptionThrown(int[] arr, int missing)
    {
        // Arrange
        var searcher = new FastSearcher();

        // Act
        Action act = () => searcher.FindIndex(arr, missing);

        // Assert
        act.Should().Throw<ItemNotFoundException>();
    }

    [Test]
    public static void FindIndex_ItemMissingInArrayOfDuplicates_ItemNotFoundExceptionThrown()
    {
        // Arrange
        var searcher = new FastSearcher();
        var arr = CreateArrayOfDuplicates(1000, 0); // Helper for large duplicate arrays
        var missing = 1;

        // Act
        Action act = () => searcher.FindIndex(arr, missing);

        // Assert
        act.Should().Throw<ItemNotFoundException>();
    }

    [Test]
    public static void FindIndex_ItemOutOfRange_ItemNotFoundExceptionThrown()
    {
        // Arrange
        var searcher = new FastSearcher();
        var arr = Helper.GetSortedArray(1000);
        var smaller = Helper.GetItemSmallerThanAllIn(arr);
        var bigger = Helper.GetItemBiggerThanAllIn(arr);

        // Act & Assert
        Action act1 = () => searcher.FindIndex(arr, smaller);
        Action act2 = () => searcher.FindIndex(arr, bigger);

        act1.Should().Throw<ItemNotFoundException>();
        act2.Should().Throw<ItemNotFoundException>();
    }

    private static int[] CreateArrayOfDuplicates(int length, int value)
    {
        var arr = new int[length];
        Array.Fill(arr, value);
        return arr;
    }
}