题目：
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