LeetCode（力扣）——Search in Rotated Sorted Array 搜索旋转排序数组 python实现
2020-12-13 13:44
标签：asc 中文 sort python complex tar 否则 ack etc 题目描述： python实现 Search in Rotated Sorted Array 搜索旋转排序数组 中文：假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。 你可以假设数组中不存在重复的元素。 你的算法时间复杂度必须是 O(log n) 级别。 英文：Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm‘s runtime complexity must be in the order of O(log n). 题目来源：力扣题库 LeetCode（力扣）——Search in Rotated Sorted Array 搜索旋转排序数组 python实现 标签：asc 中文 sort python complex tar 否则 ack etc 原文地址：https://www.cnblogs.com/spp666/p/11536041.html 1 class Solution(object):
2 def search(self, nums, target):
3 """
4 :type nums: List[int]
5 :type target: int
6 :rtype: int
7 """
8 start = 0
9 end = len(nums)-1
10 while startend:
11 mid = (start + end)/2 #对于整数会自动省去小数部分
12 if nums[mid] == target:
13 return mid
14 if nums[mid]>=nums[start]:
15 if target >= nums[start] and targetnums[mid]:
16 end = mid-1
17 else:
18 start = mid + 1
19
20 if nums[mid]nums[end]:
21 if target > nums[mid] and targetnums[end]:
22 start = mid+1
23
24 else:
25 end = mid -1
26 return -1
文章标题：LeetCode（力扣）——Search in Rotated Sorted Array 搜索旋转排序数组 python实现
文章链接：http://soscw.com/essay/33282.html