33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

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

 1 class Solution {
 2     public int search(int[] nums, int target) {
 3         if (nums.length == 0) return -1;
 4         int n = nums.length;
 5         int l = 0, r = n - 1;
 6         while (l < r) {
 7             int mid = (l + r) >> 1;
 8             if (nums[mid] > nums[r]) {
 9                 l = mid + 1;
10             } else {
11                 r = mid;
12             }
13         }
14         System.out.println(l);
15         int offset = l;
16         l = 0;
17         r = n - 1;
18         while (l < r) {
19             int mid = (l + r) >> 1;
20             //System.out.println(l + " " + mid + " " + r);
21             if (target < nums[(mid + offset) % n]) {
22                 r = mid - 1;
23             } else if(target > nums[(mid + offset) % n]) {
24                 l = mid + 1;
25                 
26             } else {
27                 return (mid + offset) % n;
28             }
29         }
30         
31         return nums[(l + offset) % n] == target ? (l + offset) % n : -1;
32         
33     }
34 }

 1 class Solution {
 2     public int check(int[] nums, int target, int s, int e) {
 3         
 4         
 5         int l = s, r = e;
 6         while (l < r) {
 7             int mid = (l + r) >> 1;
 8             if (target < nums[mid]) {
 9                 r = mid - 1;
10             } else if (target > nums[mid]) {
11                 l = mid + 1;
12                 
13             } else {
14                 return mid;
15             }
16         }
17         
18         System.out.println("l = " + l);
19         return nums[l] == target ? l : -1;
20         
21     }
22     public int search(int[] nums, int target) {
23         int n = nums.length;
24         if (n == 0) return -1;
25         int l = 0, r = n - 1;
26         while (l < r) {
27             int mid = (l + r) >> 1;
28             if (nums[l] < nums[mid]) {
29                 int temp = check(nums, target, l, mid);
30                 if (temp != -1) {
31                     return temp;
32                 } else {
33                     l = mid + 1;
34                 }
35             } else {
36                 int temp = check(nums, target, mid + 1, r);
37                 if (temp != -1) {
38                     return temp;
39                 } else {
40                     r = mid;
41                 }
42             }
43         }
44         return nums[l] == target ? l : -1;
45         
46     }
47 }