tìm phần tử tối thiểu trong một mảng được sắp xếp theo chu kỳ

Question

Tôi đã thử mã sau đây để tìm ra phần tử tối thiểu trong một mảng được sắp xếp theo chu kỳ. Nhưng nó thất bại khi thấp = 1 và cao = 2 bởi vì giữa luôn luôn là 1 và [mid] = a [1] luôn lớn hơn [high].

Tôi đang cố gắng sử dụng Tìm kiếm nhị phân tại đây để tìm giải pháp.

//finding the minim element in the cyclic sorted array 
int arrC[]={10,13,1,3,4,5,8}; 
int low=0,high =6; 
int mid=0,reset =1; 
while (low < high) 
{ 
    mid = (low+ high)/2; 
    if (arrC[mid]>arrC[high]) 
    { 
     low = mid; 
    } 
    else if (arrC[mid] < arrC[high]) 
    { 
     high = mid; 

    } 
} 
printf("minimum element is %d",arrC[mid+1]); 

Answer 1

Sử dụng tìm kiếm nhị phân bình thường, nhưng nếu arrC[high] < arrC[low], điều trị arrC[high] như vô cực để giải thích cho các bọc xung quanh. Để làm điều đó chỉ cần thay đổi dòng:

if (arrC[mid]>arrC[high]) 

tới:

if (arrC[high] < arrC[low] || arrC[mid] > arrC[high]) 

Answer 2

Có 2 vấn đề với mã của bạn

• Như đã chỉ bởi Paulpro ... điều trị arrC [cao] như vô cùng ..
• Ngoài ra, tôi cũng khuyên bạn nên sử dụng

mid = low + (high-low)/2;

Không sử dụng (low+high)/2. Điều này có thể làm cho số tiền vượt quá giới hạn số nguyên và sẽ dẫn đến giá trị âm. Một lý do nữa khiến mã của bạn có thể bị lỗi.

Answer 3

#include <stdio.h> 

int main(void){ 
//finding the minim element in the cyclic sorted array 
    int arrC[]={10,13,1,3,4,5,8}; 
    int low=0, high = sizeof(arrC)/sizeof(*arrC)-1; 
    int range; 
    if(arrC[low]>=arrC[high]){ 
     while (range = (high - low)/2){// range = range/2; 
      if(arrC[high - range] <= arrC[high]){ 
       high -= range; 
      } else { 
       low = high - range; 
       continue; 
      } 
      if(arrC[low] <= arrC[low + range]){ 
       low += range; 
      } else { 
       high = low + range; 
      } 
     } 
     if(high == low + 1){ 
      low = high; 
     } 
    } 
    printf("minimum element is %d",arrC[low]);//1 
    return 0; 
} 

lưu ý: Không thể chia một nửa phạm vi tìm kiếm đơn giản khi cùng một giá trị được bao gồm trong dữ liệu đã đặt hàng nếu không thể xác định hướng được tìm kiếm dễ dàng. Nhưng có thể nếu cùng một giá trị không được bao gồm.