Repository navigation
[FEATURE REQUEST] Add Search in Rotated Sorted Array implementation with JUnit tests #7579
Description
Activity
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.
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!
Reacted by Dark's DevilHi @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!
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!
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!
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?
@Vivek-ML001 yes, works for me.
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