Массив содержит N отсортированных подмножеств, которые находятся в неправильном порядке. Найти элемент X в массиве

Question

Рассмотрим Arr [5] = {4,5, 1,2,3};Здесь массив имеет два отсортированных подмножества. Один - {4,5}, а другой - {1,2,3}. Мне нужно найти элемент X (любой элемент) в массиве с минимальной временной сложностью.

PS: мне нужна только логика для этой проблемы. Заранее спасибо.

До сих пор я могу думать о сортировке массива по времени O (n * logn) и поиске по времени двоичного поиска O (logn). Но есть ли другая эффективная логика поиска X?

Answer 1

Сложность O (logN) при бинарном поиске

    int Arr[5]={4,5,1,2,3},l=0,r=4,mid,X,ans=-1;
    cin>>X;

Инициализация массива Arr , по которому мы выполняем бинарный поиск.
X - это число, которое мы пытаемся найти, l = 0 и r = sizeof (Arr) -1
ans - это индекс X, -1, если его нет в массиве.

У нас есть два условия, когда данный X будет вВ первой половине мы обновим r до середины 1.

Случай 1. Точка вращения находится в первой половине, а также X.
(Arr [l]> Arr [mid] && (X> = Arr [l] || X <= Arr [mid])) </em>

Обеспечиваетэта точка вращения находится в первой половине Arr [l]> Arr [mid], и если X> = Arr [l], то X может быть только в первой половине, а X <= Arr [mid], тогда X также может быть только в первойполовина. <br>

Случай 2. Точка вращения находится во второй половине, но X находится в первой половине
(Arr [l] <= Arr [mid] &&(X> = Arr [l] && X <= Arr [mid])) </em>

Если Arr [mid] == X, обновите ответ и прервите цикл.

    while(l<=r){
        cout<<l<<r<<" ";
        mid=(l+r)/2;
        if(Arr[mid]==X){
            ans=mid;
            break;
        }
        if((Arr[l] > Arr[mid] && (X>=Arr[l] || X<=Arr[mid])) 
           || (Arr[l]<=Arr[mid] && (X>=Arr[l] && X<=Arr[mid])))
            r=mid-1;
        else
            l=mid+1;
    }
    cout<<ans;