'''
leetcode 33
在以某个索引位置为中心，对数组进行旋转后，得到算法的输入数组
给定目标值，要求以时间复杂度 O(log N) 从旋转数组中查找出目标值
如果找不到，则返回-1，找到，则返回目标值在旋转后的数组的位置
算法：
首先根据target目标值和数组第一个和最后一个元素的大小比较，确定搜索的方向
如果target>nums[0] and target<nums[-1]
说明当前的数组是升序排列的，故而应该从start=0，从前向后搜索
如果target>nums[0] and target>nums[-1]
说明当前数组是类似与 4 5 6 7 0 1 2 的形式，也应该start=0，从前向后搜索
如果target<nums[0] and target<nums[-1]
则应该从后向前搜索，end=len(nums)-1
如果target<nums[0] and target>nums[-1]
则无论是对于升序数组还是前升序后降序的数组，都无法搜索，返回-1
'''
class Solution:
def search(self, nums, target: int) -> int:
if(len(nums)==0):
return -1
if(len(nums)==1):
if nums[0]==target:
return 0
else:
return -1
start=0
end=len(nums)-1
start_status=True
end_status=True
if (start_status and end_status):
if nums[start]==target:
return start
if nums[end]==target:
return end
if nums[start]>target and nums[end]>target:#说明应该从后向前搜索
start_status=False
elif nums[start]>target and nums[end]<target:
return -1
else:
end_status = False
# elif nums[start]<target and nums[end]<target:#说明应该从前向后搜索
# end_status=False
# else:
# print(start_status,end_status)
if start_status:
start+=1
# print(start)
while(start<len(nums) and nums[start]>=nums[start-1]):
while(nums[start]==nums[start-1]):
start+=1
if nums[start]==target:
return start
elif nums[start]<target:
start+=1
else:
return -1
return -1
if end_status:
end-=1
while(end>=0 and nums[end]<=nums[end+1]):
while(nums[end]==nums[end+1]):
end-=1
if nums[end]==target:
return end
elif nums[end]>target:
end-=1
else:
return -1
return -1
if __name__=="__main__":
print(Solution().search([1,3,5],3))
上述算法在最坏的情况下仍然是线性复杂度。
Runtime: 36 ms, faster than 94.74% of Python3 online submissions forSearch in Rotated Sorted Array.
'''
33. Search in Rotated Sorted Array
题目中要求的时间复杂度是 O(log N)，很容易联想到二分查找
https://www.bilibili.com/video/av46411485?from=search&seid=10565559742785267521
'''
class Solution:
def search(self, nums, target: int) -> int:
if len(nums)==0:
return -1
if len(nums)==1:
if nums[0]==target:
return 0
else:
return -1
start=0
end=len(nums)-1
while(start<end):
if nums[start]==target:
return start
if nums[end]==target:
return end
mid=(start+end)//2
if nums[mid]==target:
return mid
elif nums[mid]>target:
if nums[0]<nums[mid]:# mid落在大子数组中
if target>nums[mid]:
end=mid-1
else:
start=mid+1
else:# mid落在小子数组中
if target>nums[mid]:
