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.

链接：https://leetcode.com/problems/search-in-rotated-sorted-array/#/description

4/14/2017

23ms，4%

注意：

第13行开始的情况不能简单的判断，整体被划分了3个区间。如果没有第9，10行的判断，就需要在第14，15行跟首尾比较时加上相等的情况。(!不是那么简单的，＝要在连续区间里，比如说按照下面的写法第14行不应该＝，第17行应该＝，原因是14行是2段区间，17行是连续的)

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

按照直观的写法：15ms, 58%。排除网络因素，为什么performance变化这么大？我做的改变：

1. 去掉了和lo，hi相等的判断，并且更改了第12行，15行的判断（没有大变化）

2. 将第12行，13行调整顺序（大变化，也许就是or --> and少判断一步的区别？）

 1 public class Solution {
 2     public int search(int[] nums, int target) {
 3         if (nums.length == 0) return -1;
 4         int lo = 0, hi = nums.length - 1;
 5         int mid;
 6         
 7         while (lo <= hi) {
 8             mid = lo + (hi - lo) / 2;
 9             if (target == nums[mid]) return mid;
10             else {
11                 if (nums[lo] <= nums[mid]) {
12                     if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;
13                     else lo = mid + 1;
14                 } else {
15                     if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
16                     else hi = mid - 1;
17                 }
18             }
19         }
20         return -1;
21     }
22 }

别人相同思路，但是performance好很多，15ms，主要是最后第23行的判断

 1 public int search(int[] A, int target) {
 2     if (A.length == 0) return -1;
 3     int lo = 0;
 4     int hi = A.length - 1;
 5     while (lo < hi) {
 6         int mid = (lo + hi) / 2;
 7         if (A[mid] == target) return mid;
 8         
 9         if (A[lo] <= A[mid]) {
10             if (target >= A[lo] && target < A[mid]) {
11                 hi = mid - 1;
12             } else {
13                 lo = mid + 1;
14             }
15         } else {
16             if (target > A[mid] && target <= A[hi]) {
17                 lo = mid + 1;
18             } else {
19                 hi = mid - 1;
20             }
21         }
22     }
23     return A[lo] == target ? lo : -1;
24 }

其他人的解法：

非常好的思路，将不合格的区间视为-inf, inf，不需要改值，但是可以以＝作为nums[mid]来判断。

https://discuss.leetcode.com/topic/34491/clever-idea-making-it-simple

https://discuss.leetcode.com/topic/34467/pretty-short-c-java-ruby-python

 1 int search(vector<int>& nums, int target) {
 2     int lo = 0, hi = nums.size();
 3     while (lo < hi) {
 4         int mid = (lo + hi) / 2;
 5         
 6         double num = (nums[mid] < nums[0]) == (target < nums[0])
 7                    ? nums[mid]
 8                    : target < nums[0] ? -INFINITY : INFINITY;
 9                    
10         if (num < target)
11             lo = mid + 1;
12         else if (num > target)
13             hi = mid;
14         else
15             return mid;
16     }
17     return -1;
18 }

4/25/2017

算法班

思路
用二分法，判断target的区间。

用这个方法来做这道题！
如果A[mid] > A[start]并且target在它们之间，往前找。否则往后找。注意后面还是一个Sorted Array！
如果A[mid] < A[end]并且target在它们之间，往后找。否则往前找。注意前面还是一个Sorted Array！

 1 public class Solution {
 2     /** 
 3      *@param A : an integer rotated sorted array
 4      *@param target :  an integer to be searched
 5      *return : an integer
 6      */
 7     public int search(int[] A, int target) {
 8         // write your code here
 9         if (A == null || A.length == 0) return -1;
10         
11         int start = 0, end = A.length - 1;
12         
13         while (start + 1 < end) {
14             int mid = start + (end - start) / 2;
15             if (A[mid] == target) return mid;
16             else if (A[start] < A[mid]) {
17                 if (A[start] <= target && target < A[mid]) {
18                     end = mid;
19                 } else {
20                     start = mid;
21                 }
22             } else {
23                 if (A[mid] < target && target <= A[end]) {
24                     start = mid;
25                 } else {
26                     end = mid;
27                 }
28             }
29         }
30         if (A[start] == target) return start;
31         if (A[end] == target) return end;
32         return -1;
33     }
34 }