Учитывая вращающийся сортированный массив, как я могу найти наибольшее значение в этом массиве?

Question

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

Пример:

[5, 7, 11, 1, 3] возвратит 11.

[7, 9, 15, 1, 3] возвратит 15.

Answer 1

Вы должны бинарно искать в умном способе достижения O (lg n). Обратите внимание, что элемент справа от элемента max является min (или none, если массив вообще не вращается). Так что сделайте регулярный двоичный поиск, но проверьте, что элемент в середине индекса является максимальным, если не сравнивать первый и последний элементы в каждом из левых/правых подмассивов. Если first<last в левом подмассиве, вы знаете, что левый подмассива сортируется и идет вправо, иначе вы идете влево.

Предположим, что массив называется a и имеет n элементов.

/* check if not rotated at all */ 
int ans = INFINITY; 
if(a[0] < a[n-1] || n == 1) 
{ ans = a[n-1]; 
    return; 
} 

/* array is certainly rotated */ 
int l = 0, r = n-1; 
while(r - l > 5) 
{ int m = (l + r)/2; 
    if(a[m] > a[m+1]) { ans = a[m]; break; } 
    else 
    { if(a[l] < a[m-1]) l = m+1; 
     else r = m-1; 
    } 
} 

/* check the remaining elements (at most 5) in a loop */ 
if(ans == INFINITY) 
{ for(int i = l; i <= r; i++) 
    { ans = max(ans, a[i]); 
    } 
} 

Я не тестировал этот код. Причина, по которой я разбиваюсь, когда число элементов равно 5 или меньше, состоит в том, чтобы убедиться, что количество элементов в любом подмассиве не менее 2 (так что вы можете быть уверены, что первый и последний не являются одним и тем же элементом). Вы должны попробовать это сами и исправить, если есть что исправить. Надеюсь это поможет.

Answer 2

Используйте модифицированный двоичный поиск, чтобы исключить половину отсортированного подмассива (если есть два отсортированных подмассива, удалите «нижний» подмашину) на каждом шаге, отслеживая потенциально обновленный максимум.

#include <iostream> 
#include <cstdlib> 
#include <vector> 

int main(int argc, char** argv) 
{ 
    std::vector<int> nums; 
    for(int i = 1; i < argc; i++) 
     nums.push_back(atoi(argv[i])); 

    int start = 0; 
    int end = argc - 2; 
    int max = nums[start]; 
    while(start <= end) { 
     int mid = (start + end) >> 1; 
     int cand; 
     if(nums[start] <= nums[mid]) { 
      start = mid + 1; 
     } else { 
      end = mid - 1; 
     } 
     cand = nums[mid]; 
     if(cand > max) 
      max = cand; 
    } 
    std::cout << max << std::endl; 
    return 0; 
}