UpperBoundTest.java

packagecom.thealgorithms.searches;

importstaticorg.junit.jupiter.api.Assertions.assertEquals;
importstaticorg.junit.jupiter.api.Assertions.assertTrue;

importjava.util.Random;
importorg.junit.jupiter.api.BeforeEach;
importorg.junit.jupiter.api.Test;

classUpperBoundTest {

privateUpperBoundupperBound;
privateInteger[] sortedArray;

@BeforeEach
voidsetUp() {
upperBound = newUpperBound();

// Generate a sorted array of random integers for testing
Randomrandom = newRandom();
intsize = 100;
intmaxElement = 100;
sortedArray = random.ints(size, 1, maxElement)
 .distinct() // Ensure all elements are unique
 .sorted()
 .boxed()
 .toArray(Integer[] ::new);
 }

@Test
voidtestUpperBoundFound() {
intkey = sortedArray[sortedArray.length - 1] + 1; // Test with a key larger than max element
intindex = upperBound.find(sortedArray, key);

// The upper bound should be equal to the length of the array
assertEquals(sortedArray.length - 1, index, "Upper bound for a larger key should be the size of the array.");
 }

@Test
voidtestUpperBoundExactMatch() {
intkey = sortedArray[sortedArray.length / 2]; // Choose a key from the middle of the array
intindex = upperBound.find(sortedArray, key);

// The index should point to the first element greater than the key
assertTrue(index < sortedArray.length, "Upper bound should not exceed array length.");
assertTrue(sortedArray[index] > key, "The element at the index should be greater than the key.");
 }

@Test
voidtestUpperBoundMultipleValues() {
Integer[] arrayWithDuplicates = newInteger[] {1, 1, 2, 3, 4, 4, 5, 6, 7, 8, 9}; // Test array with duplicates
intkey = 4;
intindex = upperBound.find(arrayWithDuplicates, key);

assertTrue(index < arrayWithDuplicates.length, "Upper bound index should be valid.");
assertEquals(6, index, "The upper bound for 4 should be the index of the first 5.");
assertTrue(arrayWithDuplicates[index] > key, "Element at the upper bound index should be greater than the key.");
 }

@Test
voidtestUpperBoundLowerThanMin() {
intkey = 0; // Test with a key lower than the minimum element
intindex = upperBound.find(sortedArray, key);

assertEquals(0, index, "Upper bound for a key lower than minimum should be 0.");
assertTrue(sortedArray[index] > key, "The element at index 0 should be greater than the key.");
 }

@Test
voidtestUpperBoundHigherThanMax() {
intkey = sortedArray[sortedArray.length - 1] + 1; // Test with a key higher than maximum element
intindex = upperBound.find(sortedArray, key);

assertEquals(sortedArray.length - 1, index, "Upper bound for a key higher than maximum should be the size of the array.");
 }

@Test
voidtestUpperBoundEdgeCase() {
// Edge case: empty array
Integer[] emptyArray = {};
intindex = upperBound.find(emptyArray, 5);

assertEquals(0, index, "Upper bound for an empty array should be 0.");
 }

@Test
voidtestUpperBoundSingleElementArray() {
Integer[] singleElementArray = {10};
intindex = upperBound.find(singleElementArray, 5);

assertEquals(0, index, "Upper bound for 5 in a single element array should be 0.");

index = upperBound.find(singleElementArray, 10);
assertEquals(0, index, "Upper bound for 10 in a single element array should be 0.");

index = upperBound.find(singleElementArray, 15);
assertEquals(0, index, "Upper bound for 15 in a single element array should be 0.");
 }
}