Package g0001_0100.s0033_search_in_rotated_sorted_array

Class Solution

java.lang.Object

g0001_0100.s0033_search_in_rotated_sorted_array.Solution

public class Solution
extends Object

33 - Search in Rotated Sorted Array.<p>Medium</p> <p>There is an integer array <code>nums</code> sorted in ascending order (with <strong>distinct</strong> values).</p> <p>Prior to being passed to your function, <code>nums</code> is <strong>possibly rotated</strong> at an unknown pivot index <code>k</code> (<code>1 <= k < nums.length</code>) such that the resulting array is <code>[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]</code> ( <strong>0-indexed</strong> ). For example, <code>[0,1,2,4,5,6,7]</code> might be rotated at pivot index <code>3</code> and become <code>[4,5,6,7,0,1,2]</code>.</p> <p>Given the array <code>nums</code> <strong>after</strong> the possible rotation and an integer <code>target</code>, return <em>the index of</em> <code>target</code> <em>if it is in</em> <code>nums</code><em>, or</em> <code>-1</code> <em>if it is not in</em> <code>nums</code>.</p> <p>You must write an algorithm with <code>O(log n)</code> runtime complexity.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> nums = [4,5,6,7,0,1,2], target = 0</p> <p><strong>Output:</strong> 4</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> nums = [4,5,6,7,0,1,2], target = 3</p> <p><strong>Output:</strong> -1</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> nums = [1], target = 0</p> <p><strong>Output:</strong> -1</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= nums.length <= 5000</code></li> <li><code>-10⁴ <= nums[i] <= 10⁴</code></li> <li>All values of <code>nums</code> are <strong>unique</strong>.</li> <li><code>nums</code> is an ascending array that is possibly rotated.</li> <li><code>-10⁴ <= target <= 10⁴</code></li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	search(int[] nums, int target)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

search

public int search(int[] nums,
 int target)