算法要求：数组元素先严格递减后严格递增，请设计一段尽可能高效的算法找出最小元素。
思路：采用分治的思想。
int FindMin(int Buff[],int start,int end)
{
if (end==start)
{
return Buff[start];
}
int mid = (start+end)/2;
//后半段
if (Buff[mid]<Buff[mid+1]&&Buff[mid-1]<Buff[mid])
{
return FindMin(Buff,start,mid-1);
} //中间段
else if (Buff[mid]<Buff[mid+1]&&Buff[mid-1]>Buff[mid])
{
return Buff[mid];
}//前面段
else if(Buff[mid]>Buff[mid+1]&&Buff[mid-1]>Buff[mid])
{
return FindMin(Buff,mid+1,end);
}
}
以下是python的递归和非递归版本
@print_result_after
def findmin(data):
start = 0
end = len(data)
mid = 0
while start < end:
mid = (start + end)//2
print('{start},{end}:{mid}-{data}'.format(start = start,end = end,mid=mid,data=data[mid]))
# 同时这里不能是>=，因为只有一个的时候会死循环
if data[start] > data[mid]:
# 要保留mid，这里mid可能是最小值，不能是mid+1，比如data=[1,0]
start = mid
else:
# 这里不要mid，mid不可能是最小值
end = mid
return data[mid]
def findmin(data,start,end):
if start > end:
return False
if start == end - 1:
return data[start]
mid = (start + end) // 2
if data[start] > data[mid]:
start = mid
else:
end = mid
return findmin(data,start,end)
