33. Search in Rotated Sorted Array

题目：

Suppose a sorted array 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.

链接： http://leetcode.com/problems/search-in-rotated-sorted-array/

题解：Rotated array中查找值，使用Binary Search，要注意数组是向左shift或者是向右shift，保持在一个单调递增的部分进行查找。

简单的三种情况 - 1) 不平移 1234567

　　　　　　　　2) 向左3位 4567123

　　　　　　 3) 向右3位 5671234

时间复杂度 O(logn)，空间复杂度 O(1)

public class Solution {
    public int search(int[] nums, int target) {         //binary search
        if(nums == null || nums.length == 0)
            return 0;
        int lo = 0, hi = nums.length - 1;
        
        while(lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if(nums[mid] == target)
                return mid;
            else if(nums[mid] < nums[hi]) {            // right half sorted
                if(target > nums[mid] && target <= nums[hi])        //e.g. target = 5,  1-2-3-4-5-6-7,  6-7-1-2-3-4-5
                    lo = mid + 1;
                else                                                //e.g  target = 5,  5-6-7-1-2-3-4
                    hi = mid - 1;
            } else {                                  // left half sorted
                if(target < nums[mid] && target >= nums[lo])        //e.g. target = 3,  3-4-5-6-7-1-2
                    hi = mid - 1;
                else                                                //e.g. target = 3,  4-5-6-7-1-2-3 
                    lo = mid + 1;
            }
        }
        
        return -1;
    } 
}

二刷:

Java:

反而写得比较复杂了。不过原理就是用nums[mid]和nums[right]进行比较，保持mid左边或者右边一段是有序的，再根据target与 nums[mid] 和nums[right]的关系来完成进一步的二分。看到3天前StefanPochmann又发了一个帖子，可以加入Integer.MIN_VALUE或者Integer.MAX_VALUE来进行普通二分，非常巧妙，放在reference里以后看。

Time Complexity - O(logn)， Space Complexity - O(1)

public class Solution {
    public int search(int[] nums, int target) { // assume no duplicates
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (target == nums[mid]) {
                return mid;
            } else if (target < nums[mid]) {
                if (nums[mid] < nums[hi]) {  // right part sorted
                    hi = mid - 1;
                } else{
                    if (target <= nums[hi]) {
                        lo = mid + 1;
                    } else {
                        hi = mid - 1;
                    }
                }
            } else {
                if (nums[mid] < nums[hi]) {
                    if (target > nums[hi]) {
                        hi = mid - 1;
                    } else {
                        lo = mid + 1;
                    }
                } else {
                    lo = mid + 1;
                }
            }
        }
        return -1;
    }
}

题外话：

今天被Two Sigma的Recruiter联系，聊了一下之后感觉对方十分专业。打算递交简历以后再拖延一段时间，来进行复习准备。更需要练习的是反应速度，脑力，分析能力，交流能力，专注程度，以及做题的速度和准确度。

三刷:

使用了一刷的逻辑。还是Binary Search，就是先判断是否nums[mid] == target，再判断这个sorted array是向左还是右平移，哪一部分仍然是有序的。接下来根据上面的信息来判断如何二分。

Java:

Time Complexity - O(logn)， Space Complexity - O(1)。

public class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (target == nums[mid]) {
                return mid;
            } else if (nums[mid] < nums[lo]) {  // right side sorted
                if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;
                else hi = mid - 1;
            } else {                              // left side sorted
                if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;
                else lo = mid + 1;
            }
        }
        return -1;
    }
}

4/3/2016: 今天去Edison取税，之后和地图君一块吃了一家H-Mart附近的东北菜馆。人很少，周日中午加上我们一共就三桌，不过味道挺不错。吃了烤羊肉串，豆腐脑，煎饼果子，韭菜盒子，锅包肉，地三鲜，酸菜排骨等等，特别对我的胃口。咸豆腐脑可能还是来美帝这么久第一次吃到，好羡慕住附近的朋友们。地图君坚持付了帐，下次再这样我要生气了。

Reference:

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

https://leetcode.com/discuss/41134/java-ac-solution-using-once-binary-search