[leetcode]033-Search in Rotated Sorted Array[二分查找]

本文主要是介绍[leetcode]033-Search in Rotated Sorted Array[二分查找]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 原题

https://leetcode.com/problems/search-in-rotated-sorted-array/

2. 思路

题意：一个有序列表在某个位置前后两部分被调换，求出给定值的索引下标。

思路：题目要求时间复杂度log(n), 显然要用二分法。

我们依然考虑中间值n[mid]， 如果其小于最右值，那么右部分是有序的。

否则左部分有序。这样不断在某部分查找即可。

3. 源码

class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums)-1while left <= right:mid = (left + right)//2if (nums[mid] == target):return midelif nums[mid] < nums[right]: #right part is orderedif target > nums[mid] and target <= nums[right]:left = mid+1else:right = mid-1else: #left part is orderedif target >= nums[left] and target < nums[mid]:right = mid-1else:left = mid+1return -1

 

这篇关于[leetcode]033-Search in Rotated Sorted Array[二分查找]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---