Để tìm phần tử tối thiểu trong một mảng được sắp xếp và xoay

Question

Gần đây tôi đã gặp sự cố lập trình như sau:

Một mảng được sắp xếp được cung cấp và mảng được xoay tại một số điểm chưa biết, tôi phải tìm yếu tố tối thiểu trong đó. Mảng cũng có thể chứa các bản sao.

Đối với ví dụ:

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

Output: 1 

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

Output: 0 

Tôi đi theo giải pháp đơn giản là để đi qua trough mảng đầy đủ và tìm tối thiểu. Giải pháp này đòi hỏi thời gian O (n) .Tôi hiểu thực tế là yếu tố tối thiểu là phần tử có phần tử trước đó lớn hơn nó. Nếu không có yếu tố như vậy, thì không có vòng quay và phần tử đầu tiên sẽ là tối thiểu.

Nhưng tôi đã được yêu cầu giải pháp O (Đăng nhập). Có cách nào để giải quyết nó trong thời gian O (Logn) không?

Answer 1

Off đỉnh đầu của tôi:

• Note entry đầu tiên
• Thực hiện một tìm kiếm nhị phân; ở mỗi giai đoạn, chọn nửa bên phải nếu phần tử trục lớn hơn hoặc bằng phần tử đầu tiên được lưu trữ và nửa bên trái nếu phần tử trục nhỏ hơn.

Ví dụ, cho {4,5,6,7,1,2,3}:

• Pivot tại 7>4, giảm một nửa đúng {1,2,3}
• Pivot tại 2 < 4, giảm một nửa trái 1.
• Chỉ xem xét một phần tử, câu trả lời là 1.

Answer 2

xem điều này: Vì đó là mảng được sắp xếp. tôi cần phải áp dụng tìm kiếm nhị phân để tìm trục xoay.

Yếu tố thấp nhất sẽ là nơi mảng được xoay vòng.

Gọi 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); 
}