LintCode Q62 Search in Rotated Sorted Array optimised in Python

  • Jinhai ZHOU
  • 3 Minutes
  • 2016年12月25日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
"""
@param A : a list of integers
@param target : an integer to be searched
@return : an integer
"""
def search(self, A, target):
# write your code here
# no duplicates
# time complexity: O(log(n))
lo, hi = 0, len(A) - 1
while lo <= hi:
mid = lo + (hi - lo)/2
if A[mid] == target:
return mid
elif (A[lo] < A[mid] and A[lo] <= target and target < A[mid]) or (A[mid] < A[lo] and not (A[mid] < target and target <= A[hi])):
hi = mid - 1
else:
lo = mid + 1
return -1
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。