Python binary search solution - O(logn) - 48ms


  • 15
    G
    class Solution:
        # @param {integer[]} numss
        # @param {integer} target
        # @return {integer}
        def search(self, nums, target):
            if not nums:
                return -1
    
            low, high = 0, len(nums) - 1
    
            while low <= high:
                mid = (low + high) / 2
                if target == nums[mid]:
                    return mid
    
                if nums[low] <= nums[mid]:
                    if nums[low] <= target <= nums[mid]:
                        high = mid - 1
                    else:
                        low = mid + 1
                else:
                    if nums[mid] <= target <= nums[high]:
                        low = mid + 1
                    else:
                        high = mid - 1
    
            return -1

  • -1
    E

    mid = (low + high) / 2 can get you integer overflow, I prefer mid = low + (high-low)/2


  • 0
    N

    @eran there is no integer overflow in python


  • 0
    B

    Isn't that we need to sort the array in ascending order first..?


Log in to reply
 

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