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


  • 17
    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..?


  • 0

    @bdeng3 then this question is pointless


  • 0
    L

    @jedihy not pointless, the question ask for the index so you cannot sort the array because it changes index


Log in to reply
 

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