时间戳

首页 > 解决方案 > 在主题二分搜索下的 InterviewBit 问题中，在 C++ 中旋转排序数组中的搜索超过了时间限制

c++ - 在主题二分搜索下的 InterviewBit 问题中，在 C++ 中旋转排序数组中的搜索超过了时间限制

问题描述

问题是在 C++ 中的已排序、旋转数组中搜索元素。我使用的方法是找到枢轴元素索引/最小元素索引，然后从 a[pivot......end] 或 a[beg,....pivot] 使用二进制找到键搜索。

找到最小元素索引的时间复杂度是 O(log n)，然后找到元素也是 O(log n)，因此总体时间复杂度将是 O(log n)

但是我收到了 Time Limit Exceeded 错误这是我的代码：

int find_pivot(std::vector<int> a, int beg, int end)
{
    while(beg<=end)
    {
        int mid=(beg+end)/2;
        if(mid>0 && a[mid]<a[mid-1])
            return mid;
        else if(a[mid]>a[end])
            beg=mid+1;
        else
            end=mid;
    }
}

int search_element(std::vector<int> a, int key, int beg, int end)
{
    int pivot = find_pivot(a,0,a.size()-1);
    if(key>=a[pivot] && key<=a[end])
        beg=pivot;
    else
        end=pivot;
    while(beg<=end)
    {
        int mid=(beg+end)/2;
        if(key==a[mid])
            return mid;
        else if(key>a[mid])
            beg=mid+1;
        else
            end=mid-1;
    }
    return -1;
}

int Solution::search(const vector<int> &A, int B) {
    int n = A.size();
   int i = search_element(A, B, 0, n-1); 

    if (i != -1) 
    return i;
    else
    return -1;
}

标签： c++arraysalgorithmdata-structurestime-complexity

解决方案

检查您的 find_pivot 函数，假设数组通常按 [1,2,3,4,5] 排序。现在，当您调用 find_pivot 函数时，将会出现 beg=0 和 end =1 的时间。

现在，由于 mid=(beg+end/2)=0 您的函数将更改 end=mid ，这意味着 end 也变为 0。

现在你的 beg=0 和 end=0，现在当循环再次开始时 Mid = 0+0/2 并且这将继续重复。

进行一些更改，我认为问题在于数组何时正常排序或 end=begin。

推荐阅读