这是一道经过稍稍改动的二分查找题，二分法算是分治思想最基础的算法了，而在LeetCode上的这道题对二分法稍加修改后摇身一变成了medium题。记得大一时期碰到这道题稍加思考便解决了，而前几天看到这道题时还在纸上演算了好久，嗯，拿小本本记下来。
LeetCode原题如下：leetcode 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 = 0Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3Output: -1
题意
在基于升序数组的情况下进行元素循环左移（或理解成循环右移，rotated as some pivot unknown）所得到的数组在O（log N）时间复杂度下完成目标元素target查找。
解决思路分析
时间复杂度限定意味着需要在原有二分查找法体系下对rotated情况下的数组进行一定的分析处理。根据原有二分法思想我们知道其关键在于判断查找元素处于参考点（mid）的左边还是右边，进而不断缩小查找范围以达到在有序数组下的高效搜索。同样的，在此的关键在于判断所需要查找元素target处在mid下标的左区域[left,mid]还是右区域[mid,right]。因为数组rotate排列的原因，目标元素是否在某个区间（left or right Side）有两种情况需要分析。在此对元素是否在左半段（isLeftSide）的判断情况进行分析，第一种情况是左半段数组元素完全有序，即nums[left]<nums[mid]，并且target>=nums[left] && target<=nums[mid]即可判定target处在左半段，和普通的二分查找判断几乎一致；另一种情况是左半段元素序列包含rotated交接段（pivot）（例如其中一种情况:{8, 9, 1, 2, 3, 4, 5 , 6, 7 }，target=1）,此时对于左半段元素区间判断有多种情况需要分析，若是正面去刚（分析）会有很多不必要的损耗，在此我们知道“target处在左半段”与“target处在右半段”是一个对立事件，此外当rotated交接处（pivot）在左半段时意味着右半段处于完全有序（有序情况下判断target是否在此区间是比较容易的），此时我们只要判定了target不在右半段即可知道其在左半段（代码：(mid<=right && !(target>=mid && target<=right))）。
综上即可得到target类二分查找判断算法，代码如下（faster than 100% on LeetCode）：
public static int search2(int[] nums, int target) {int left=0;int right=nums.length-1;while(left<=right) {int mid=left+(right-left)/2;if(nums[mid]==target) {return mid;}//just as a normal binary after L/R side judgeif(isLeftSide(nums[left],nums[right],nums[mid],target)) {//judge whether the target in the left or right side. right=mid-1;}else {left=mid+1;}}return -1;}private static boolean isLeftSide(int left,int right,int mid,int target) {/*** left,mid and right as a judge reference, which base on ascend order.* the key is which judge the side, left or right in position of mid.* ok, in this problem, in the ascend order with rotate, we just focus on normal order judge.*/
// return ((left<=mid && (target>=left && target<=mid)) || (mid<=right && (target<mid || target>right)));return ((left<=mid && (target>=left && target<=mid)) || (mid<=right && !(target>=mid && target<=right)));}
总结：
一开始看到题采用的是“正面刚”分析法，然后绕了一圈才发现上面的“对立事件”转移分析法（两个词自编的，为了增加理解记忆，咋们程序员也需要点自娱自乐嘛_，嘿嘿），“你看，最好的方法就在眼皮子底下却视而不见”。对，废话一大堆，想说的就一句话：选对分析方法很重要！