Repository: TheAlgorithms/Java
Pull request #5665 (2024-10-09 06:24:07)

Add tests, remove `main`, improve docs in `FibonacciSearch`
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index cc4e90a4..0726337c 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -1001,6 +1001,7 @@
             * [BM25InvertedIndexTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/BM25InvertedIndexTest.java)
             * [BreadthFirstSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/BreadthFirstSearchTest.java)
             * [DepthFirstSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/DepthFirstSearchTest.java)
+            * [FibonacciSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/FibonacciSearchTest.java)
             * [HowManyTimesRotatedTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/HowManyTimesRotatedTest.java)
             * [KMPSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/KMPSearchTest.java)
             * [OrderAgnosticBinarySearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/OrderAgnosticBinarySearchTest.java)
diff --git a/src/main/java/com/thealgorithms/searches/FibonacciSearch.java b/src/main/java/com/thealgorithms/searches/FibonacciSearch.java
index 028ab07e..2124938b 100644
--- a/src/main/java/com/thealgorithms/searches/FibonacciSearch.java
+++ b/src/main/java/com/thealgorithms/searches/FibonacciSearch.java
@@ -2,24 +2,42 @@ package com.thealgorithms.searches;
 
 import com.thealgorithms.devutils.searches.SearchAlgorithm;
 
-/*
- *  Fibonacci Search is a popular algorithm which finds the position of a target value in
- *  a sorted array
+/**
+ * FibonacciSearch is a search algorithm that finds the position of a target value in
+ * a sorted array using Fibonacci numbers.
  *
- *  The time complexity for this search algorithm is O(log3(n))
- *  The space complexity for this search algorithm is O(1)
- *  @author Kanakalatha Vemuru (https://github.com/KanakalathaVemuru)
+ * <p>
+ * The time complexity for this search algorithm is O(log n).
+ * The space complexity for this search algorithm is O(1).
+ * </p>
+ *
+ * <p>
+ * Note: This algorithm requires that the input array be sorted.
+ * </p>
  */
 public class FibonacciSearch implements SearchAlgorithm {
 
     /**
-     * @param array is a sorted array where the element has to be searched
-     * @param key is an element whose position has to be found
-     * @param <T> is any comparable type
-     * @return index of the element
+     * Finds the index of the specified key in a sorted array using Fibonacci search.
+     *
+     * @param array The sorted array to search.
+     * @param key The element to search for.
+     * @param <T> The type of the elements in the array, which must be comparable.
+     * @throws IllegalArgumentException if the input array is not sorted or empty, or if the key is null.
+     * @return The index of the key if found, otherwise -1.
      */
     @Override
     public <T extends Comparable<T>> int find(T[] array, T key) {
+        if (array.length == 0) {
+            throw new IllegalArgumentException("Input array must not be empty.");
+        }
+        if (!isSorted(array)) {
+            throw new IllegalArgumentException("Input array must be sorted.");
+        }
+        if (key == null) {
+            throw new IllegalArgumentException("Key must not be null.");
+        }
+
         int fibMinus1 = 1;
         int fibMinus2 = 0;
         int fibNumber = fibMinus1 + fibMinus2;
@@ -57,15 +75,12 @@ public class FibonacciSearch implements SearchAlgorithm {
         return -1;
     }
 
-    // Driver Program
-    public static void main(String[] args) {
-        Integer[] integers = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
-
-        int size = integers.length;
-        Integer targetValue = 128;
-        FibonacciSearch fsearch = new FibonacciSearch();
-        int atIndex = fsearch.find(integers, targetValue);
-
-        System.out.println("Should be found: " + targetValue + ". Found " + integers[atIndex] + " at index " + atIndex + ". An array length " + size);
+    private boolean isSorted(Comparable[] array) {
+        for (int i = 1; i < array.length; i++) {
+            if (array[i - 1].compareTo(array[i]) > 0) {
+                return false;
+            }
+        }
+        return true;
     }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/searches/FibonacciSearchTest.java b/src/test/java/com/thealgorithms/searches/FibonacciSearchTest.java
new file mode 100644
index 00000000..801c33b1
--- /dev/null
+++ b/src/test/java/com/thealgorithms/searches/FibonacciSearchTest.java
@@ -0,0 +1,124 @@
+package com.thealgorithms.searches;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+import java.util.stream.IntStream;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Unit tests for the FibonacciSearch class.
+ */
+class FibonacciSearchTest {
+
+    /**
+     * Test for basic Fibonacci search functionality.
+     */
+    @Test
+    void testFibonacciSearchFound() {
+        FibonacciSearch fibonacciSearch = new FibonacciSearch();
+        Integer[] array = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
+        int key = 128;
+        int expectedIndex = 7; // Index of the key in the array
+        assertEquals(expectedIndex, fibonacciSearch.find(array, key), "The index of the found element should be 7.");
+    }
+
+    /**
+     * Test for Fibonacci search when the element is not present.
+     */
+    @Test
+    void testFibonacciSearchNotFound() {
+        FibonacciSearch fibonacciSearch = new FibonacciSearch();
+        Integer[] array = {1, 2, 4, 8, 16};
+        int key = 6; // Element not present in the array
+        int expectedIndex = -1; // Key not found
+        assertEquals(expectedIndex, fibonacciSearch.find(array, key), "The element should not be found in the array.");
+    }
+
+    /**
+     * Test for Fibonacci search with the first element as the key.
+     */
+    @Test
+    void testFibonacciSearchFirstElement() {
+        FibonacciSearch fibonacciSearch = new FibonacciSearch();
+        Integer[] array = {1, 2, 4, 8, 16};
+        int key = 1; // First element
+        int expectedIndex = 0; // Index of the key in the array
+        assertEquals(expectedIndex, fibonacciSearch.find(array, key), "The index of the first element should be 0.");
+    }
+
+    /**
+     * Test for Fibonacci search with the last element as the key.
+     */
+    @Test
+    void testFibonacciSearchLastElement() {
+        FibonacciSearch fibonacciSearch = new FibonacciSearch();
+        Integer[] array = {1, 2, 4, 8, 16};
+        int key = 16; // Last element
+        int expectedIndex = 4; // Index of the key in the array
+        assertEquals(expectedIndex, fibonacciSearch.find(array, key), "The index of the last element should be 4.");
+    }
+
+    /**
+     * Test for Fibonacci search with a single element present.
+     */
+    @Test
+    void testFibonacciSearchSingleElementFound() {
+        FibonacciSearch fibonacciSearch = new FibonacciSearch();
+        Integer[] array = {1};
+        int key = 1; // Only element present
+        int expectedIndex = 0; // Index of the key in the array
+        assertEquals(expectedIndex, fibonacciSearch.find(array, key), "The index of the single element should be 0.");
+    }
+
+    /**
+     * Test for Fibonacci search with a single element not present.
+     */
+    @Test
+    void testFibonacciSearchSingleElementNotFound() {
+        FibonacciSearch fibonacciSearch = new FibonacciSearch();
+        Integer[] array = {1};
+        int key = 2; // Key not present
+        int expectedIndex = -1; // Key not found
+        assertEquals(expectedIndex, fibonacciSearch.find(array, key), "The element should not be found in the array.");
+    }
+
+    /**
+     * Test for Fibonacci search with an empty array.
+     */
+    @Test
+    void testFibonacciSearchEmptyArray() {
+        FibonacciSearch fibonacciSearch = new FibonacciSearch();
+        Integer[] array = {}; // Empty array
+        int key = 1; // Key not present
+        assertThrows(IllegalArgumentException.class, () -> fibonacciSearch.find(array, key), "An empty array should throw an IllegalArgumentException.");
+    }
+
+    @Test
+    void testFibonacciSearchUnsortedArray() {
+        FibonacciSearch fibonacciSearch = new FibonacciSearch();
+        Integer[] array = {2, 1, 4, 3, 6, 5};
+        int key = 3; // Key not present
+        assertThrows(IllegalArgumentException.class, () -> fibonacciSearch.find(array, key), "An unsorted array should throw an IllegalArgumentException.");
+    }
+
+    @Test
+    void testFibonacciSearchNullKey() {
+        FibonacciSearch fibonacciSearch = new FibonacciSearch();
+        Integer[] array = {1, 2, 4, 8, 16};
+        Integer key = null; // Null key
+        assertThrows(IllegalArgumentException.class, () -> fibonacciSearch.find(array, key), "A null key should throw an IllegalArgumentException.");
+    }
+
+    /**
+     * Test for Fibonacci search on large array.
+     */
+    @Test
+    void testFibonacciSearchLargeArray() {
+        FibonacciSearch fibonacciSearch = new FibonacciSearch();
+        Integer[] array = IntStream.range(0, 10000).boxed().toArray(Integer[] ::new); // Array from 0 to 9999
+        int key = 9999;
+        int expectedIndex = 9999;
+        assertEquals(expectedIndex, fibonacciSearch.find(array, key), "The index of the last element should be 9999.");
+    }
+}