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


  • 21
    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


  • 1
    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


  • 0
    W
    This post is deleted!

  • 0
    W

    Can anyone give me an idea about the boundary cases? like if noms[low] <= target <<nums[mid] , why we can use double "<=" here?
    I am really confused about this in binary search problem. If someone could piont me to some reference to clear this question, that would be great !


Log in to reply
 

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