问题：
使用二分法在循环递增序列中查找指定元素，返回其下标；若不存在，则返回-1.要求时间复杂度为：O(logN)。
循环递增序列的定义：
nums = [7,8,9,10,1,2,3,4,5,6]
即，一个序列被分为两个子序列，每个子序列都是递增的，并且如果在指定位置（如“10”，“1”之间）切断重组，则可以变为递增序列。
思路：
注意：由于时间复杂度要求为 O(logN)，则不能使用先找到断点的方法（若先找到断点，则时间复杂度必然大于O(N)）。
一、我们回想一下用二分法查找递增序列：
def fun0(nums,target): start = 0 end = len(nums)-1 mid = (start+end)/2 while start<=end: if target==nums[mid]: return mid if target<nums[mid]: end = mid-1 else: start = mid+1 mid = (start+end)/2 return -1 nums = [i for i in range(10)] print fun0(nums,1)具体不做赘述，主要思路是每次将列表切成两段，然后继续查找。二、在处理循环递增列表时，我们依旧将列表先切成两段（每一个矩形代表一个递增子序列），切完之后会产生A、B两种情况：
A情况，断点位于第一个递增子序列之中，则待查找值target 可能位于上图(1)区域，或者(2)区域；若target位于(1)区域中，则可以用二分法查找；若不在，则对(2)继续切割；
B情况，断点位于第二子序列中，待查找target可能位于(3)或(4)；若target位于(4)区域，则用二分法；其余情况同上。
总结：每次切割，都可以得到一个递增序列和一个循环递增序列，当发现target为递增序列中时，则可以使用二分法查找，否则，继续切割循环递增序列。
def fun(nums,target): start = 0 end = len(nums)-1 while start<=end: mid = (start+end)/2 if target==nums[mid]: return mid if nums[start]<nums[mid]: #A情况 if target>=nums[start] and target<=nums[mid]: #（1）区间 end = mid-1 else: #（2）区间 start = mid+1 if nums[mid]<nums[end]: #B情况 if target>=nums[mid] and target<=nums[end]: #（4）区间 start = mid+1 else: #（3）区间 end = mid-1 return -1 nums = [7,8,9,10,1,2,3,4,5,6] print fun(nums,4)
