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

Abierto
#7,579 12 comentarios 0 reacciones 2 asignados Ver en GitHub

Los mantenedores suelen responder en 1 día

@Pratik5545 ya está trabajando en esto.

Desde el 3/11/2026.

Evaluación

Este issue todavía no se ha evaluado.

Descripción

enhancement
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

Lenguaje dominante
Java
Estrellas
67.2k
Forks
21.5k
Merge medio
2 d 5 h
PR fusionados (30 d)
42

Preparar el entorno

Abrir en Codespaces

Inicia el contenedor de desarrollo del proyecto en tu navegador, con tu propia cuenta de GitHub.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de TheAlgorithms/Java

Todos los issues de TheAlgorithms/Java

Issues similares

Más issues de Java

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.