本文主要是介绍[LeetCode] 33. Search in Rotated Sorted Array @ python，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一．题目：
有一个不含重复数字的升序数组，可能做了一些旋转操作，给定一个数查询是否存在这个数，若存在返回下标否则返回-1.时间复杂度为O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
二．解题思路：
要求时间复杂度O(log n)，提示我们使用二分搜索．这里要注意中间数字所在的区间是属于左边升序区间还是右边升序区间．代码如下：
class Solution(object):def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""#时间复杂度为O(log n),则考虑使用二分查找if not nums:return -1start = 0end = len(nums)-1while start <= end:mid = (start+end)/2if nums[mid] == target:return mid#当nums[mid]属于左边升序序列时if nums[mid] >= nums[start]:if target>=nums[start] and target<nums[mid]:end = mid -1else:start = mid +1#当nums[mid]属于右边升序序列时elif nums[mid] <= nums[end]:if target<=nums[end] and target>nums[mid]:start = mid +1else:end = mid -1return -1
如果这个数字可以包含重复数字，也就是leetcode上第81题，是上题的升级版．我们可以将其简化为上一题的版本，具体操作就是判断首尾两个元素是否相等，若不相等则将左指针一直往右移动．代码如下：
class Solution(object):def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: bool"""N = len(nums)l, r = 0, N - 1while l <= r:while l < r and nums[l] == nums[r]:l += 1mid = l + (r - l) / 2if nums[mid] == target:return Trueif nums[mid] >= nums[l]:if nums[l] <= target < nums[mid]:r = mid - 1else:l = mid + 1elif nums[mid] <= nums[r]:if nums[mid] < target <= nums[r]:l = mid + 1else:r = mid - 1return False
这篇关于[LeetCode] 33. Search in Rotated Sorted Array @ python的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
