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

オープン
#7,579 コメント 12 件 リアクション 0 件 担当者 2 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

@Pratik5545 がすでに取り組んでいます。

2026年11月3日 から。

評価

この issue はまだ評価されていません。

説明

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

主要言語
Java
スター
67.2k
フォーク
21.5k
平均マージ
2日 5時間
マージ済み PR(30日)
42

環境構築

Codespaces で開く

このプロジェクトの開発コンテナを、あなたの GitHub アカウントでブラウザ上に起動します。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

TheAlgorithms/Java のほかの issue

TheAlgorithms/Java の issue をすべて見る

似ている issue

Java の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。