Превышено ограничение по времени для поиска в повернутом отсортированном массиве в C ++ в проблеме InterviewBit при topi c Binary Search

Question

Проблема заключается в поиске элемента в отсортированном, повернутом массиве в C ++. Подход, который я использовал, заключается в том, чтобы найти индекс сводного элемента / минимальный индекс элемента, а затем найти ключ либо из [pivot ...... end], либо из [beg, .... pivot] использовать двоичный файл. поиск.

Сложность по времени для нахождения минимального индекса элемента составляет O (log n), а затем для нахождения элемента также O (log n), и, следовательно, общая сложность по времени будет O (log n)

Но я получаю сообщение об ошибке превышения лимита времени Вот мой код:

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;
}

Answer 1

Проверьте вашу функцию 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, теперь, когда l oop начинается снова Mid = 0 + 0/2, и это будет повторяться.

Внесите некоторые изменения, и я думаю, что проблема в том, когда массив обычно сортируется или когда end = begin .