Find the minimum element in a sorted and rotated array

Question

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]

Ray Jasson · Accepted Answer · 2020-08-08 04:45:26Z

4

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.

edited Aug 8, 2020 at 4:45

answered Aug 7, 2020 at 17:13

Ray Jasson

4802 gold badges12 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Find the minimum element in a sorted and rotated array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related