在列表中找到最小的数字

Question

我正在尝试查找列表中的最小数字。列表中的数字可以是：

   1. decrease first and then increase (won't decrease again)
           [5,3,2,0,1,6,99]

   2. or increase only
           [3,4,5,6,7,8]

   3. or decrease only
           [8,6,4,3,2]

数字大于等于0

我唯一可以使用的是将当前号码与它的前一个号码和下一个号码进行比较。但它太慢了。有没有O(logN)甚至更快的方法？

Answer 1

二分法的变体仍然有效，具有对数复杂度。

测试前两个数字。如果它们在增加，你就完成了。
测试最后两个数字。如果它们在减少，你就完成了。
否则，范围的左侧是递减斜率，右侧是递增斜率。一分为二，select 与属性相同的一半。继续，直到范围缩小到 1 个元素。

Answer 2

基于问题约束，只需在 O(1) 时间复杂度内比较序列的开始或结束两个元素，就可以找到递增或递减序列的 case-2 和 case-3。

现在，对于先有属性先减后增的情况，可以在O(logN)时间复杂度中找到，其中N是序列长度。

如果我们分析，序列如下所示：

\           /
 \         /
 (x)     (y)
   \     /
    \   /
    (ans)

因此，在执行二分搜索时，在每一步中，我们都会将搜索范围划分为一半，并根据元素的位置移动到一半。如果中间元素存在于第一个下降部分，如 x 我们可以移动到右侧，如果中间元素存在于第二个增加部分，如 y 我们可以移动到左侧。通过这种方式，我们接近答案 ans.

由于在每一步中，我们将搜索范围除以一半并向一半移动，因此解决方案的复杂度变为 O(logN)。

C++ 中的示例代码如下所示：

int findSmallest(vector<int>ar) {
   int n = ar.size();
   if (n == 1) return ar[0];
   if (ar[1] > ar[0]) return ar[0]; //Increase only condition
   if (ar[n - 1] < ar[n - 2]) return ar[n - 1]; // Decrease only condition
   int lo = 1, hi = n - 2;
   int ans;
   while (lo <= hi) {
      int mid = (lo + hi) / 2;
      if ((ar[mid] < ar[mid - 1]) && (ar[mid] < ar[mid + 1])) {
        ans = ar[mid];
        break;
      }
      if ((ar[mid] < ar[mid - 1]) && (ar[mid] > ar[mid + 1])) { //have to move right
         lo = mid + 1;
      } else {
        hi = mid - 1;
      }
   }
   return ans;
}

在列表中找到最小的数字

find the smallest number in a list

algorithm

performance

divide-and-conquer