Challenge lab in Searching Ordered and Unordered Data

Mission

Find a target in a rotated sorted array using logarithmic search.

Learning outcome: Search a rotated sorted array

Correctness contract

Invariant: The active interval contains every remaining position where the target could occur.

Required technique: Identify the normally sorted half at each midpoint, then retain only the half whose value range can contain the target.

Complexity target: time O(log n); space O(n) input.

Input and output

Input: n, then n integers, then one target integer. Whitespace may be spaces or line breaks.

Output: Print the required zero-based index as one integer. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• The array contains distinct values and is a rotation of a strictly increasing array.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Identify the normally sorted half at each midpoint, then retain only the half whose value range can contain the target.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

7 4 5 6 7 0 1 2 0

Sample output

4

Why the sample works: Visible walkthrough for the ordinary non-trivial path. At every midpoint, one sorted half is identified and kept only when its value range contains the target. Input `7 4 5 6 7 0 1 2 0` therefore produces `4`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: Write the meaning of lo and hi above the loop and verify that every update shrinks the interval.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.