Click here to Skip to main content
15,884,045 members
Please Sign up or sign in to vote.
1.22/5 (3 votes)
See more:
A list is strictly convex if its elements first decrease, then, increase. How can I write a function in python that accepts a convex list and returns its minima in time complexity O(log(n)), n being the size of the list. (NO USE OF ANY BUILT IN FUNCTIONS OVER LISTS)
Posted
Updated 14-Jun-14 3:16am
v3

1 solution

Python
def bin_search(lis,first,end):
	mid = (first+end)//2
	if (end - first)<2:
		if lis[end]>lis[first]:
			print(lis[first])
		else:
			print(lis[end])
	elif(lis[mid]>lis[mid+1]):
		bin_search(lis,mid,end)
	else:
		bin_search(lis,first,mid)


def minima(a):
	b = bin_search(a,0,len(a)-1)
	return(b)
 
Share this answer
 
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900