循環ソート配列の最小要素を見つける

Question

循環ソート配列の最小要素を見つけるために、次のコードを試してみました。しかし、中間が常に1でa [mid] = a [1]が常にa [high]より大きいため、low = 1とhigh = 2のときは失敗します。

解決策を見つけるためにここでバイナリ検索を使用しようとしています。

//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

通常のバイナリ検索を使用しますが、arrC[high] < arrC[low]場合は、ラップアラウンドを考慮するために、無限大としてarrC[high]を扱います。

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

：：ただの行を変更することを行うには

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

Answer 2

はPaulproで指摘したように、あなたのコード

• と2つの問題がある...と[高] arrCを扱います無限..
• とは別に、私はあなたに使用することをお勧めします

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

(low+high)/2を使用しないでください。これにより、合計が整数の限界を超え、負の値になります。あなたのコードが失敗するもう一つの理由。

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; 
} 

注：場合、容易に検索する方向を決定することは不可能であるため、同じ値が、順序付けられたデータに含まれている単に探索範囲を半分にすることは不可能です。しかし、同じ値が含まれていなければ可能です。