Repository navigation
[FEATURE REQUEST] Add Search in Rotated Sorted Array implementation with JUnit tests #7579
Description
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
Proposed Changes
I would like to add:
-
SearchInRotatedArray.javaundersrc/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.
- Complete implementation with clear Javadoc explanations (
-
SearchInRotatedArrayTest.javaundersrc/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]tonums[mid]) is sorted:- If sorted, check if the target falls within
nums[left]andnums[mid]. Adjustleftorrightboundaries accordingly.
- If sorted, check if the target falls within
- Otherwise, the right half must be sorted:
- Check if the target falls within
nums[mid]andnums[right]. Adjust boundaries accordingly.
- Check if the target falls within
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
Activity
Vivek-ML001 commentedon 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 commentedon 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 commentedon 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 commentedon 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:
I don't want to duplicate existing functionality, so I wanted to confirm the intended scope before proceeding. Thanks!
github-actions commentedon 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 commentedon 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:
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 commentedon Sep 28, 2026
@Vivek-ML001 yes, works for me.