Standard python binary search with explanation


  • 0
    W

    First, we need to know whether the array has been rotated. Then we can just do standard binary search, except that we need to have clear ideas where the target falls into. Say the prerotated order is a,b,c,d and we have c,d,a,b afterwards. we can be more selective by not only comparing target with elements at mid indices, but also c and b which are low and high repectively. This way we can distinguish case by case where target and mid fall into (it's either in (a,b) or (c,d)).
    '''

    def search(self, nums, target):
        if not nums: return -1
        if nums[-1] >= nums[0]:
            ret = bisect.bisect_left(nums, target)
            return ret if 0 <= ret < len(nums) and nums[ret] == target else -1
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) >> 1
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                if nums[hi] == target:
                    return hi
                elif nums[hi] > target:
                    lo = mid + 1
                else:
                    if nums[mid] <= nums[hi]:
                        hi = mid - 1
                    else:
                        lo = mid + 1
            else:
                if nums[hi] == target:
                    return hi
                elif nums[hi] < target:
                    hi = mid -1
                else:
                    if nums[mid] <= nums[hi]:
                        hi = mid - 1
                    else:
                        lo = mid + 1
        return -1
    

    '''


Log in to reply
 

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