GeezerVison is showing github.com — [FEATURE REQUEST] Add Search in Rotated Sorted Array implementation with JUnit tests · Issue #7579 · TheAlgorithms/Java
[FEATURE REQUEST] Add Search in Rotated Sorted Array implementation with JUnit tests #7579DescriptionWhat 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 ActivityVivek-ML001 commented on Aug 26, 2026 Hi, I’d like to work on this issue as my first open-source contribution. Could you please assign this issue to me? I’ll implement the rotated sorted array search along with comprehensive JUnit 5 tests and follow the project’s existing conventions.Rosander0 commented on Aug 27, 2026 Hi @sohamcodes-ctrl ,
Thanks for your interest in contributing to TheAlgorithms/Java! It's great to see you diving into open-source with such a clear plan.
Just to clarify—I'm also a contributor to this repository, not a maintainer, so I don't have the permissions to assign issues to others. The official maintainers who can handle assignments and reviews are:
That being said, I’d encourage you to go ahead and start working on the implementation if you're comfortable with the approach. Once you open a pull request, the maintainers will be able to review it and give you feedback.
Feel free to tag me if you need any help or have questions while working on it—I'll be happy to support however I can.
Looking forward to seeing your contribution! sohamcodes-ctrl commented on Aug 27, 2026 Hi @DenizAltunkapan, I’d like to work on this issue as my first open-source contribution. I’ve reviewed the requirements and understand the Binary Search approach for handling the rotated sorted array.
I can implement:
SearchInRotatedArray.java with O(log N) time and O(1) space
Comprehensive JUnit 5 tests covering rotations, edge cases, and target-not-found scenarios
Proper Javadoc, null checks, and project formatting conventions
I’ll also verify the implementation locally with the project’s test suite before submitting the PR.
Could you please assign this issue to me? I’d be happy to take it up. Thank you! sohamcodes-ctrl commented on Aug 28, 2026 Hi @Vivek-ML001, I inspected the repository before starting the implementation and noticed that RotatedBinarySearch.java already implements the Search in Rotated Sorted Array algorithm, including handling rotated/unrotated arrays, missing targets, and duplicates.
The existing implementation also provides the expected O(log N) average behavior and O(1) space complexity, with O(N) worst-case behavior when duplicates prevent determining the sorted half.
Since the issue specifically proposes adding SearchInRotatedArray.java, I wanted to confirm whether you would like me to:
- Add a separate SearchInRotatedArray.java implementation as described in the issue, or
- Improve/extend the existing RotatedBinarySearch implementation and its tests.
I don't want to duplicate existing functionality, so I wanted to confirm the intended scope before proceeding. Thanks! github-actions commented on Sep 28, 2026 This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contribution! Vivek-ML001 commented on Sep 28, 2026 Hi @sohamcodes-ctrl, thanks for checking before starting!
Since RotatedBinarySearch already covers this algorithm, I agree we shouldn't add a duplicate SearchInRotatedArray class. I suggest we go with option 2 and improve the existing implementation instead:
- Extend RotatedBinarySearchTest with missing edge cases (null/empty array, single element, target at pivot, target at both ends, all-duplicates worst case)
- Improve Javadoc (complexity, duplicates behaviour)
To avoid overlap: you take the tests, I'll take the Javadoc + any implementation cleanup (or split however you prefer). We'll open separate PRs.
@DenizAltunkapan could you confirm this scope works, or would you rather close this issue as a duplicate? DenizAltunkapan commented on Sep 28, 2026 runtimecraft-105 commented on Oct 25, 2026 Hi @DenizAltunkapan @alxkm @yanglbme,
Since there has been no activity on this for the past 2 months, I would like to take this up. I can implement SearchInRotatedArray.java along with comprehensive JUnit 5 tests.
Could you please assign this issue to me? Thanks! DenizAltunkapan commented on Oct 25, 2026 Pratik5545 commented on Nov 2, 2026 Hi @sohamcodes-ctrl and @Vivek-ML001, are you still working on the test and Javadoc improvements discussed above? I couldn’t find a related PR. If work is in progress, could you share the branch or PR so I can avoid duplicating it?
@DenizAltunkapan, if either part is available, would it be okay for me to pick it up? I’m happy to help with the remaining scope DenizAltunkapan commented on Nov 3, 2026 @Pratik5545 sure, if nobody replies. go ahead. i assigned you Pratik5545 commented on Nov 9, 2026 I checked the current master branch and found that PR #7623 already added the edge-case tests and Javadoc improvements discussed here. Is there any remaining scope for #7579, or should this issue be closed as completed?
MetadataMetadataDevelopmentNo branches or pull requestsIssue actions
|