поиск элемента в массиве, который вращается N раз

Question

У меня есть отсортированный массив, который вращается n раз, n неизвестно. Теперь я хочу найти элемент с помощью двоичного поиска в O (nlog n). Я реализовал следующий код, он работает нормально. Но я думаю, что условие if ((end-start) == 1) может быть пропущено путем внесения некоторых изменений, кто-нибудь может предложить?

Eg of array 1 2 3 4 5 
            2 3 4 5 1 //rotated once

Код:

public static int srch(int a[],int start,int end,int key){
    if(start>end)
        return -1;

    if((end-start)==1 ){
        if(key==a[start])
            return start;
        else if(key==a[end])
            return end;
        else
            return -1;
    }
    int mid = (start+end)/2;

    if(a[mid]== key){
        return mid;
    }
    else{
        if(a[start] < a[mid] ){
            //first half is sorted
            if(key>a[mid]|| key <a[start]){
                start= mid+1;
            }else{
                end =mid-1;
            }
        }else{
            //second half is sorted

            if(key>a[mid]){
                start= mid+1;
            }else{
                end =mid-1;
            }
        }
        return srch(a, start, end, key);
    }
}

Есть ли лучшее / простое / более эффективное решение?

Answer 1

Ваше решение не выполняется для массива {4,5,1,2,3} и ключа = 4. Я думаю, что модификация во второй части решит проблему

else{
            //second half is sorted

            if(key>a[mid] && key<=a[end]){// modified condition
                start= mid+1;
            }else{
                end =mid-1;
            }

Но я думаю, что условие if ((end-start) == 1) может быть пропущен вносить некоторые изменения, может любой предложить?

Полагаю, это условие вообще не требуется. Можете ли вы предложить тестовый пример, который не подходит для вашего измененного кода.

public static int srch(int a[],int start,int end,int key){
    if(start>end)
        return -1;

     int mid = (start+end)/2;

    if(a[mid]== key){
        return mid;
    }
    else{
        if(a[start] < a[mid] ){
            //first half is sorted
            if(key>a[mid]|| key <a[start]){
                start= mid+1;
            }else{
                end =mid-1;
            }
        }else{
            //second half is sorted

            if(key>a[mid] && key<=a[high]){
                start= mid+1;
            }else{
                end =mid-1;
            }
        }
        return srch(a, start, end, key);
    }
}

Answer 2

Я не проверил ваш код на предмет корректности, но ваше решение - O (log n). У вас не может быть лучшего решения алгоритмически.

Answer 3

Ваше решение работает в O (log n), поэтому не может быть более эффективного решения.Возможно, части вашего кода можно было бы оптимизировать, но это не повлияет на время выполнения с точки зрения O. Как вы сказали, код работает и возвращает правильные значения, поэтому я бы сказал, что это правильный ответ на ваш вопрос интервью.