What would you like to Propose?
Feature Description
I would like to propose adding an implementation of Search in Rotated Sorted Array in Java using the Binary Search technique.
This is a classic variation of Binary Search that achieves $\mathcal{O}(\log N)$ time complexity by checking which half of the rotated array is sorted at each step.
Proposed Changes
I would like to add:
-
SearchInRotatedArray.java under src/main/java/com/thealgorithms/searches/
- Complete implementation with clear Javadoc explanations ($\mathcal{O}(\log N)$ Time, $\mathcal{O}(1)$ Space).
- Proper null checks and edge-case handling.
-
SearchInRotatedArrayTest.java under src/test/java/com/thealgorithms/searches/
- Comprehensive JUnit 5 test suite covering standard rotations, target not found, empty arrays, and single-element arrays.
Verification
I will ensure all code follows the project's formatting rules and passes ./gradlew test / mvn test locally before opening a PR.
I would love to implement this as my first open-source contribution! Could a maintainer please assign this issue to me?
Issue details
Issue Details & Algorithm Overview
1. Algorithm Description
- Algorithm: Search in Rotated Sorted Array
- Category: Searching Algorithms / Binary Search Variation
- Language: Java
2. How the Algorithm Works
Given a sorted array of integers that has been rotated at an unknown pivot index (e.g., [0, 1, 2, 4, 5, 6, 7] becomes [4, 5, 6, 7, 0, 1, 2]), find the index of a given target element. If the element is not present, return -1.
Key Logic:
- Find the middle element using
int mid = left + (right - left) / 2; to avoid integer overflow.
- Check if the left half of the array (
nums[left] to nums[mid]) is sorted:
- If sorted, check if the target falls within
nums[left] and nums[mid]. Adjust left or right boundaries accordingly.
- Otherwise, the right half must be sorted:
- Check if the target falls within
nums[mid] and nums[right]. Adjust boundaries accordingly.
3. Complexity Analysis
-
Time Complexity: $\mathcal{O}(\log N)$ — Divides the search space in half at each iteration.
-
Space Complexity: $\mathcal{O}(1)$ — Uses constant iterative space without recursion stacks or extra memory allocation.
4. Planned Files & Folder Structure
src/main/java/com/thealgorithms/searches/SearchInRotatedArray.java (Implementation)src/test/java/com/thealgorithms/searches/SearchInRotatedArrayTest.java (JUnit 5 Test Suite)
Additional Information
No response
What would you like to Propose?
Feature Description
I would like to propose adding an implementation of Search in Rotated Sorted Array in Java using the Binary Search technique.
This is a classic variation of Binary Search that achieves$\mathcal{O}(\log N)$ time complexity by checking which half of the rotated array is sorted at each step.
Proposed Changes
I would like to add:
SearchInRotatedArray.javaundersrc/main/java/com/thealgorithms/searches/SearchInRotatedArrayTest.javaundersrc/test/java/com/thealgorithms/searches/Verification
I will ensure all code follows the project's formatting rules and passes
./gradlew test/mvn testlocally before opening a PR.I would love to implement this as my first open-source contribution! Could a maintainer please assign this issue to me?
Issue details
Issue Details & Algorithm Overview
1. Algorithm Description
2. How the Algorithm Works
Given a sorted array of integers that has been rotated at an unknown pivot index (e.g.,
[0, 1, 2, 4, 5, 6, 7]becomes[4, 5, 6, 7, 0, 1, 2]), find the index of a given target element. If the element is not present, return-1.Key Logic:
int mid = left + (right - left) / 2;to avoid integer overflow.nums[left]tonums[mid]) is sorted:nums[left]andnums[mid]. Adjustleftorrightboundaries accordingly.nums[mid]andnums[right]. Adjust boundaries accordingly.3. Complexity Analysis
4. Planned Files & Folder Structure
src/main/java/com/thealgorithms/searches/SearchInRotatedArray.java(Implementation)src/test/java/com/thealgorithms/searches/SearchInRotatedArrayTest.java(JUnit 5 Test Suite)Additional Information
No response