https://leetcode.com/problems/search-in-rotated-sorted-array/description/
// array 可以是有序的；若是无序，则二分后，其中一半必然有序，从有序的部分进行判断二分走向
class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0;
int end = nums.length - 1;
int mid;
while (start <= end) {
mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
}
// start to end is ordered
if (nums[start] <= nums[end]) {
if (nums[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
// left half is ordered
} else if (nums[start] <= nums[mid]) {
if (nums[mid] > target && nums[start] <= target) {
end = mid - 1;
} else {
start = mid + 1;
}
// right half is ordered
} else {
if (nums[mid] < target && nums[end] >= target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
}
