What's wrong with my Python binary search code?


  • 0
    C
    class Solution:
        # @param num, a list of integer
        # @return an integer
        def findMin(self, num):
            return self.getMin(num, 0, len(num)-1)
        def getMin(self, num, left, right):
            if len(num)==1:
                return num[left]
            elif len(num)==2:
                return min(num)
            mid=(left+right)//2
            
            if num[left]>num[mid]:
                return self.getMin(num, left, mid)
            elif num[left]<num[mid]:
                return self.getMin(num, mid, right)
            else:
                return num[mid]
    

    I compared it with others' and found that they should do exactly the same thing even though codes are different. Anyone knows why?

    The program aborts at [1,2,3]. By my code, it will return 2, which is not the correct answer, however looking at others' code, this part of algorithm is the same, and this should work if the array is rotated.

    What should I do to make sure the program can handle with rotated and non-rotated array?


  • 0
    H

    You need to use the num[right] information, i.e., whether num[left] or num[mid] is larger or smaller than num[right] makes a difference.


Log in to reply
 

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