c++ - 搜索复杂度优于 O(n) 的数组中的元素

Question

我有任何数组，其中元素首先按升序排列，然后按降序排列

类似于 A[10]={1,4,6,8,3,2} ，数组中没有重复项。

如果输入是7，输出应该是，元素不存在。

时间复杂度 b 优于 O(n)

我通过线性搜索获得结果，将每个元素与要找​​到的元素进行比较。但是因为我想要比 O(n) 更好的解决方案

我尝试找到数组元素翻转的枢轴，然后从(0 到枢轴元素)搜索，然后再次搜索(最后一个元素到枢轴元素)。

请推荐。对于 O(n)

 #include<iostream>
 int main()
 {
     int A[10]={1,4,6,8,3,2};
     int i,num
     cout<<"Enter the element to be searched";
     cin>>num
     for(i=0;i<10;i++)
     {
         If(A[i]==num)
        {
          cout<<"Element exist";
         break;
      }
         else
         cout<<"Element do not exist";
     }
 }

Answer 1

算法:

1. 通过二进制搜索找到 log(n) 中的最大值并保存其索引。
2. 在最大值的两侧进行二分查找。
3. 如果未找到且元素不等于最大值，则该元素不存在。

第一步怎么做？

• 选择数组的中间部分
• 对照左边的项目(你的邻居)检查它。如果更大，则 max 在右侧。否则，我们从降序开始，最大值在左侧。选择向右/向左搜索的方式取决于左边的项目是大还是小。

编辑
以防万一不清楚:如果你选择第 n/2 个元素，结果 max 在左边，那么你选择第 n/4 个元素，如果 max 在它的右边，你只继续搜索在 n/4...n/2 个元素范围内。