leetcode 33. 搜索旋转排序数组(python)

忘是亡心i 2022-05-14 12:28 210阅读 0赞

**【前言】**

python刷leetcode题解答目录索引：[https://blog.csdn.net/weixin\_40449300/article/details/89470836][https_blog.csdn.net_weixin_40449300_article_details_89470836]

github链接：[https://github.com/Teingi/test][https_github.com_Teingi_test]

**【正文】**

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 `[0,1,2,4,5,6,7]` 可能变为 `[4,5,6,7,0,1,2]` )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 `-1` 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 *O*(log *n*) 级别。

**示例 1:**

输入: nums = [4,5,6,7,0,1,2], target = 0
    输出: 4

**示例 2:**

输入: nums = [4,5,6,7,0,1,2], target = 3
    输出: -1

--------------------

### 思路：直接遍历查找的话当然最省事，但是时间复杂度是O(n),不合题意。一看到题目要求时间复杂度*O*(log *n*) 级别，就应该想到应该是用二分法了。但这题难就难在它并不是一个严格意义上的递增序列，而是两段递增序列组成的。那第一步就应该先用二分法找出分界点。然后对两段用二分法查找出index。相当于用了两次二分法。 ###

class Solution(object):
        def search(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            #先找到两个第二个升序数组的第一项的
            l = 0
            r = len(nums) -1
            while l < r:
                mid = (l + r)//2
                if nums[mid] > nums[r]:
                    l = mid + 1
                else:
                    r = mid
            pol = l
            ans = self.binary_search(target, nums[:pol])
            if ans == -1:
                ans = self.binary_search(target, nums[pol:])
                if ans != -1:
                    ans += len(nums[:pol])
     
            return ans
        # 二分查找index值函数
        def binary_search(self, target, nums):
            index = -1
            l = 0
            r = len(nums) - 1
            while l <= r:
                mid = (l+r)//2
                if nums[mid] < target:
                    l = mid + 1
                elif nums[mid] > target:
                    r = mid - 1
                else:
                    index = mid
                    break
            return index

[https_blog.csdn.net_weixin_40449300_article_details_89470836]: https://blog.csdn.net/weixin_40449300/article/details/89470836
[https_github.com_Teingi_test]: https://github.com/Teingi/test