CODEWITHSUNDEEP
pythonarrayspython-3.xdata-structuresbinary-search
Just another person
Just another person

Reputation: 447

Find the minimum element in a sorted and rotated array

The question: A sorted array A[ ] with distinct elements is rotated at some unknown point, the task is to find the minimum element in it.

Expected Time Complexity: O(Log n)
My code:

def binarySearch(arr, n): 
    s = 0
    e = n-1
    while e >= s: 
        mid = (s+e) // 2
        if e==s:
            return arr[e]
        if mid == s and arr[mid] < arr[mid+1]:
            return arr[mid]
        elif mid == e and arr[mid] < arr[mid-1]:
            return arr[mid]
        elif arr[mid] < arr[mid - 1] and arr[mid] < arr[mid+1]:
            return arr[mid]
        elif arr[mid] < arr[e]:
            e = mid - 1
        else:
            e = mid + 1

When I use the Array = [10, 20, 30, 40, 50, 5, 7], I get the answer = 10, whereas, it should be 5.
What could the error be?
EDIT: Following the answer, I also had to add the following line to consider one case that's left

if e==s:
    return arr[e]

Upvotes: 3

Views: 303

Answers (1)

Ray Jasson
Ray Jasson

Reputation: 471

Does this involve just a normal binary search?

def binarySearch(arr, n): 
    s = 0
    e = n-1
    while e >= s: 
        mid = (s+e) // 2
        if e == s:
            return arr[e]
        elif mid == s and arr[mid] < arr[mid+1]:
            return arr[mid]
        elif mid == e and arr[mid] < arr[mid-1]:
            return arr[mid]
        elif arr[mid] < arr[mid - 1] and arr[mid] < arr[mid+1]:
            return arr[mid]
        elif arr[mid] < arr[e]:
            e = mid - 1
        else:
            s = mid + 1

I think your last line should be s = mid + 1 instead of e = mid + 1.

Upvotes: 4

Related Questions