CODEWITHSUNDEEP
pythonarraysbinary-search
Shubham Aggarwal
Shubham Aggarwal

Reputation: 363

Finding the max element in an array, sorted ascending first and then descending

I tried an online challenge which had a question as follows:

You are given an array which increases at first and then starts decreasing. For example: 2 3 4 5 6 7 8 6 4 2 0 -2. Find the maximum element of these array.

Following is my code using binary search and it gives correct answer in O(log(n)) but I don't know whether there is a better solution or not. Can anyone help me with that?

a= map(int, raw_input().split())
def BS(lo,hi):
    mid = lo+ (hi-lo)/2
    if a[mid]>=a[mid+1]:
        if a[mid]>a[mid-1]:
            return mid
        else:
            return BS(lo,mid)
    else:
        return BS(mid,hi)

print a[BS(0,len(a)-1)]

Upvotes: 2

Views: 2046

Answers (3)

EDDIE VALVERDE
EDDIE VALVERDE

Reputation: 30

Why don't you use the max() method??

max(lst) will return the max value in a list

Upvotes: -1

Vidul
Vidul

Reputation: 10528

An optimised variant - twice faster in most cases:

# ® Видул Николаев Петров
a = [2, 3, 4, 5, 6, 7, 8, 10, 12, 24, 48, 12, 6, 5, 0, -1]

def calc(a):
    if len(a) <= 2:
        return a[0] if a[0] > a[1]  else a[1]

    l2 = len(a) / 2

    if a[l2 + 1] <= a[l2] and a[l2] >= a[l2 - 1]:
        return a[l2]

    if a[l2] > a[l2 + 1]:
        return calc(a[:l2+1])
    else:
        return calc(a[l2:])

print calc(a) # 48

Upvotes: 2

swarnava112
swarnava112

Reputation: 431

i am trying your code with the following input 2 3 4 5 5 8 and the answer should be 8 but the answer is 5 i am posting an image with a few more test cases enter image description here

i think u cannot run binary search on an unsorted array
the code also gives huge list of exceptions for sorted arrays

Upvotes: 1

Related Questions