Binary search in python


  • 1
    X
    class Solution(object):
        def search(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            if not nums:
                return -1
            start = 0; end = len(nums)-1
            while start + 1 < end:
                mid = (start+end)/2
                if nums[mid] == target:
                    return mid
                if nums[start] <= target < nums[mid]: 
                    end = mid
                elif nums[mid] < target <= nums[end]:
                    start = mid
                elif nums[mid] > nums[end]: # right side is pivoted
                    start = mid
                else:
                    end = mid 
            if nums[start] == target:return start
            elif nums[end] == target:return end
            return -1

Log in to reply
 

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