Apparently this is a variant of binary search. We still need to divide the array into 2 parts, but in a different condition judgement.

```
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
L = len(nums)
begin = 0
end = L - 1
mid = (begin + end)/2
while 1:
# when sub-array length is smaller then 3, just brute force (O(3))
if end - begin <= 2:
if target == nums[begin]:
return begin
elif begin + 1 < L and target == nums[begin + 1]:
return begin + 1
elif begin + 2 < L and target == nums[begin + 2]:
return begin + 2
else:
return -1
m = nums[mid]
b = nums[begin]
e = nums[end]
if m == target:
return mid
if b == target:
return begin
if e == target:
return end
# (the only) triky part.
if b > m:
if target < m or target > b:
begin = begin
end = mid - 1
elif target > m or target < b:
begin = mid + 1
end = end
elif b < m:
if target < m and target > b:
begin = begin
end = mid - 1
else:
begin = mid + 1
end = end
mid = (begin + end)/2
```