[FEATURE REQUEST] Add Search in Rotated Sorted Array implementation with JUnit tests

[Dhanshri07-tech]

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:

1. 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.
2. 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:

1. Find the middle element using int mid = left + (right - left) / 2; to avoid integer overflow.
2. 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.
3. 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