# 33. Search in Rotated Sorted Array

## Problem

{% embed url="<https://leetcode.com/problems/search-in-rotated-sorted-array/description/>" %}

## Intuition

Since the array is rotated, we cannot eliminate left or right half just like that. We need to check which half we need to eliminate.

* To check if the first half is sorted

```java
nums[low] <= nums[mid] // It means left half is sorted
```

* In other cases, it means right half is sorted

Once we know which part of the array we need to search, we check if the given target is in range&#x20;

* If the target is in left part, then search towards left, else right
* If target is in right part, then search towards right, else left

## Time Complexity

`O(log n)`

## Space Complexity

`O(n)`

## Solution

```java
class Solution {
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        int result = -1;

        while(low <= high) {
            int mid = low + (high-low)/2;

            if(nums[mid] == target) { // Target found
                return mid;
            }

            if(nums[low] <= nums[mid]) { // Left sorted
                if(nums[low] <= target && target < nums[mid]) { // Search left
                    high = mid - 1;
                } else { // Search towards right
                    low = mid + 1;
                }
            } else { // Right sorted
                if(nums[mid] < target && target <= nums[high]) { // Search right
                    low = mid + 1;
                } else { // Search towards left
                    high = mid - 1;
                }
            }
        }
        return result;
    }
}
```