найти минимальный элемент в массиве, который сортируется и вращали

Question

недавно я столкнулась с проблемой программирования, которая выглядит следующим образом:

отсортированный массив задается и массив вращается в какой-то неизвестной точке, я должен найти минимальный элемент в нем. Массив также может содержать дубликаты.

Для например:

Input: {5, 6, 1, 2, 3, 4} 

Output: 1 

Input: {2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2} 

Output: 0 

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

Но меня попросили решение O (Logn). Есть ли способ решить проблему в O (Logn)?

Answer 1

Off верхней части моей головы:

• Обратите внимание на первую запись
• Perform бинарный поиск; на каждом этапе выберите правую половину, если элемент поворота больше или равен сохраненному первому элементу, а левая половина - если элемент поворота меньше.

Например, при {4,5,6,7,1,2,3}:

• Pivot в 7>4 сводятся к правой половине {1,2,3}
• поворачивающейся на 2 < 4 сводятся к левой половине 1.
• Учитывая только один элемент, ответ 1.

Answer 2

посмотреть это: Поскольку это отсортированный массив. Мне нужно применить двоичный поиск, чтобы найти pivot.

Самый низкий элемент будет там, где массив был повернут.

Вызывай эту findpivot(arr,0,n-1);

int findPivot(int arr[], int low, int high) 
{ 
    // base cases 
    if (high < low) return -1; 
    if (high == low) return low; 

    int mid = (low + high)/2; /*low + (high - low)/2;*/ 
    if (mid < high && arr[mid] > arr[mid + 1]) 
    return mid; 
    if (mid > low && arr[mid] < arr[mid - 1]) 
    return (mid-1); 
    if (arr[low] >= arr[mid]) 
    return findPivot(arr, low, mid-1); 
    else 
    return findPivot(arr, mid + 1, high); 
}