# 1-pass binary search in Python, 11 lines, 50 ms

• ``````class Solution(object):
def search(self, nums, target):
left, right = 0, len(nums)-1

while left<=right:
mid = left+(right-left)/2
lv, mv, rv = nums[left], nums[mid], nums[right]

if lv<target<mv or mv<lv<target or target<mv<rv:
right = mid-1
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``````

• 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 decrease `right`.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.