search - 在一组中找到最大值

Question

如果我有一个数字列表，其中数字增加到一个点然后在该点之后减少，是否存在有限数量的猜测，与我必须做出的集合大小无关才能找到最大值？

值之间的距离是任意的，并且增加侧的值的数量可以不同于减少侧的值的数量。

最好的方法是什么？检查元素 1，然后是最后一个元素，然后是中间的一半？并重复？或者更复杂的东西？

这种算法的处理时间是多少？

Answer 1

您可以根据列表中的元素数量尝试类似于有序搜索的递归算法。

伪代码：

List search(int index, List listpart){
   if(listpart.length()==1){ // already found
       return listpart
   }
   else if(listpart(index+1)>listpart(i) && listpart(index-1)<listpart(i)){ //search right part
      List listpart_tmp = getlistpart(listpart, index, listpart.length())
      return search(index+(listpart.length()/4), listpart_tmp
   }
   else if(listpart(index+1)<listpart(i) && listpart(index-1)>listpart(i)){ //search left part
      List listpart_tmp = getlistpart(listpart, 0, index)
      return search(index-(listpart.length()/4), listpart_tmp
   }
   else if(listpart(index+1)<listpart(i) && listpart(index-1)<listpart(i)){ //found 
      return getlistpart(listpart, index, index)
   }
}

功能

getlistpart

是一个函数，它返回一个列表，该列表由给定索引之间的原始列表中的元素组成。

Answer 2

您可以使用二分搜索将两个相邻元素而不是一个元素与固定值进行比较。从 a := 0, b := n, i := (a+b)/2 开始，比较 element(i) 和 element(i+1)。如果你注意到 e(i+1) > e(i)，你就知道断点在 i 之后，所以设置 a := i。如果 e(i) < e(i-1)，则相反，你设置 b := i。

复杂度将是 O(log n)。它会比常规的二进制搜索稍微慢一些，因为您需要更多的比较。