> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](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).

# 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 %}