Repository: TheAlgorithms/Java
Pull request #4747 (2023-10-09 14:23:34)

Update BinarySearch.java
Added iterative binary search

<!--
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] -->

- [ ] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [ ] This pull request is all my own work -- I have not plagiarized it.
- [ ] All filenames are in PascalCase.
- [ ] All functions and variable names follow Java naming conventions.
- [ ] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [ ] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

sunilnitdgp: @siriak Please review this one as well.
sunilnitdgp: @siriak updated PerfectBinarySearch's implementation and added test cases as well.

Patch:
diff --git a/src/main/java/com/thealgorithms/searches/PerfectBinarySearch.java b/src/main/java/com/thealgorithms/searches/PerfectBinarySearch.java
index bfeb5efc..495e2e41 100644
--- a/src/main/java/com/thealgorithms/searches/PerfectBinarySearch.java
+++ b/src/main/java/com/thealgorithms/searches/PerfectBinarySearch.java
@@ -1,28 +1,54 @@
 package com.thealgorithms.searches;
 
-class PerfectBinarySearch {
+import com.thealgorithms.devutils.searches.SearchAlgorithm;
 
-    static int binarySearch(int[] arr, int target) {
-        int low = 0;
-        int high = arr.length - 1;
+/**
+ * Binary search is one of the most popular algorithms The algorithm finds the
+ * position of a target value within a sorted array
+ *
+ * <p>
+ * Worst-case performance O(log n) Best-case performance O(1) Average
+ * performance O(log n) Worst-case space complexity O(1)
+ *
+ * @author D Sunil (https://github.com/sunilnitdgp)
+ * @see SearchAlgorithm
+ */
 
-        while (low <= high) {
-            int mid = (low + high) / 2;
+public class PerfectBinarySearch<T> implements SearchAlgorithm {
 
-            if (arr[mid] == target) {
-                return mid;
-            } else if (arr[mid] > target) {
-                high = mid - 1;
+    /**
+     * @param array is an array where the element should be found
+     * @param key is an element which should be found
+     * @param <T> is any comparable type
+     * @return index of the element
+     */
+    @Override
+    public <T extends Comparable<T>> int find(T[] array, T key) {
+        return search(array, key, 0, array.length - 1);
+    }
+
+    /**
+     * This method implements the Generic Binary Search iteratively.
+     *
+     * @param array The array to make the binary search
+     * @param key   The number you are looking for
+     * @return the location of the key, or -1 if not found
+     */
+    private static <T extends Comparable<T>> int search(T[] array, T key, int left, int right) {
+        while (left <= right) {
+            int median = (left + right) >>> 1;
+            int comp = key.compareTo(array[median]);
+
+            if (comp == 0) {
+                return median; // Key found
+            }
+
+            if (comp < 0) {
+                right = median - 1; // Adjust the right bound
             } else {
-                low = mid + 1;
+                left = median + 1; // Adjust the left bound
             }
         }
-        return -1;
-    }
-
-    public static void main(String[] args) {
-        int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
-        assert PerfectBinarySearch.binarySearch(array, -1) == -1;
-        assert PerfectBinarySearch.binarySearch(array, 11) == -1;
+        return -1; // Key not found
     }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/searches/PerfectBinarySearchTest.java b/src/test/java/com/thealgorithms/searches/PerfectBinarySearchTest.java
new file mode 100644
index 00000000..0ba0b03b
--- /dev/null
+++ b/src/test/java/com/thealgorithms/searches/PerfectBinarySearchTest.java
@@ -0,0 +1,43 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import com.thealgorithms.searches.PerfectBinarySearch;
+import org.junit.jupiter.api.Test;
+
+/**
+ * @author D Sunil (https://github.com/sunilnitdgp)
+ * @see PerfectBinarySearch
+ */
+public class PerfectBinarySearchTest {
+
+    @Test
+    public void testIntegerBinarySearch() {
+        Integer[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+        PerfectBinarySearch<Integer> binarySearch = new PerfectBinarySearch<>();
+
+        // Test cases for elements present in the array
+        assertEquals(0, binarySearch.find(array, 1)); // First element
+        assertEquals(4, binarySearch.find(array, 5)); // Middle element
+        assertEquals(9, binarySearch.find(array, 10)); // Last element
+        assertEquals(6, binarySearch.find(array, 7)); // Element in the middle
+
+        // Test cases for elements not in the array
+        assertEquals(-1, binarySearch.find(array, 0)); // Element before the array
+        assertEquals(-1, binarySearch.find(array, 11)); // Element after the array
+        assertEquals(-1, binarySearch.find(array, 100)); // Element not in the array
+    }
+
+    @Test
+    public void testStringBinarySearch() {
+        String[] array = {"apple", "banana", "cherry", "date", "fig"};
+        PerfectBinarySearch<String> binarySearch = new PerfectBinarySearch<>();
+
+        // Test cases for elements not in the array
+        assertEquals(-1, binarySearch.find(array, "apricot")); // Element not in the array
+        assertEquals(-1, binarySearch.find(array, "bananaa")); // Element not in the array
+
+        // Test cases for elements present in the array
+        assertEquals(0, binarySearch.find(array, "apple")); // First element
+        assertEquals(2, binarySearch.find(array, "cherry")); // Middle element
+        assertEquals(4, binarySearch.find(array, "fig")); // Last element
+    }
+}