# 33. Search in Rotated Sorted Array

![](/files/-M6wEEZ49Rlw0yqpRqT9)

### Solution

Case 1: no rotated, just do binary search as regular

Case 2: is rotated, find the pivot, and do binary search in one of two parts

Consider edge case: 0 element

#### How to find the pivot? 

```python
if nums[mid] < left:
    left = left
    right = mid
else:
    left = mid
    right = right
```

#### Better solution:

1. find the smallest element in the array which is the pivot.
2. only search left or right part of this array by Binary Search

{% tabs %}
{% tab title="Python" %}

```python
// Some code
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # find the pivot, which is smallest element in the list
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
                
        pivot = left
        left = 0
        right = len(nums) - 1
        # [1, 3], target = 3, then the pivot is 0 but not 2, so search consider right part first
        if target >= nums[pivot] and target <= nums[right]:
            left = pivot
        else:
            right  = pivot
            
        # binary search
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
                
        return -1
```

{% endtab %}

{% tab title="Java I" %}

```java
// Some code
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left)/2;
            if(nums[mid] > nums[right])
                left = mid + 1;
            else
                right = mid;
        }
        System.out.print(left);
        int pivot = left;
        left = 0;
        right = nums.length - 1;
        
        if(target >= nums[pivot] & target <= nums[right])
            left = pivot;
        else
            right = pivot;
        
        return search(nums, target, left, right);
    }
    
    public int search(int[] nums, int target, int left, int right) {
        // edge case
        if(left > right)
            return -1;
        
        // regular case
        int mid = left + (right - left)/2;
        if(nums[mid] == target)
            return mid;
        else if(nums[mid] > target)
            return search(nums, target, left, mid - 1);
        else
            return search(nums, target, mid + 1, right);
    }
}
```

{% endtab %}

{% tab title="Java II (more efficient)" %}

```java
// Some code
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = left + (right - left)/2;
            if(nums[mid] == target)
                return mid;
            // [start, mid] not rotated
            // [3, 1] is rotated, but only put here make sense
            else if(nums[mid] >= nums[left]) {
                if(target >= nums[left] && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            // [start, mid] is rotated
            else {
                if(target > nums[mid] && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
        return -1;
    }
}
```

{% endtab %}
{% endtabs %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/binary-search/33.-search-in-rotated-sorted-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.