class Solution(object):
def search(self, nums, target):
left, right = 0, len(nums)1
while left<=right:
mid = left+(rightleft)/2
lv, mv, rv = nums[left], nums[mid], nums[right]
if lv<target<mv or mv<lv<target or target<mv<rv:
right = mid1
elif lv<mv<target or target<rv<mv or mv<target<rv:
left = mid+1
else:
break
return left if target==lv else mid if target==mv else right if target==rv else 1
1pass binary search in Python, 11 lines, 50 ms


There are only 3 relationship of the nums[left], nums[mid], nums[right].
When target is not matching any middle or end points, target can locate in two intervals of the 3 cases, so total six cases. Denoting:lv, mv, rv, t = nums[left], nums[mid], nums[right], target
We have
lv < mv < rv t t mv < rv < lv t < t rv < lv < mv t <t
Those 6 cases can be classified to two actions either increase the
left
or decreaseright
.