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

  • 1
    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
            return left if target==lv else mid if target==mv else right if target==rv else -1

  • 0

    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.

Log in to reply

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