33. Search in Rotated Sorted Array#

 1class Solution {
 2
 3  public int search(int[] nums, int target) {
 4    int left = 0, right = nums.length - 1;
 5
 6    while (left <= right) {
 7      int mid = (left + right) / 2;
 8      if (nums[mid] == target) {
 9        return mid;
10      }
11
12      if (nums[left] <= nums[mid]) {
13        if (target > nums[mid] || target < nums[left]) {
14          left = mid + 1;
15        } else {
16          right = mid - 1;
17        }
18      } else {
19        if (target < nums[mid] || target > nums[right]) {
20          right = mid - 1;
21        } else {
22          left = mid + 1;
23        }
24      }
25    }
26
27    return -1;
28  }
29}

Time Complexity

Space Complexity

\(\mathcal{O}(\log{n})\)

\(\mathcal{O}(1)\)