5

I have tried the following code to find out the minimum element in a cyclic sorted array. But it fails when the low = 1 and high =2 because the mid is always 1 and a[mid]=a[1] is always greater than the a[high].

I am trying to use Binary Search here to find the solution.

//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]);
4

3 回答 3

3

你的代码有2个问题

  • 正如Paulpro所指出的......将 arrC[high] 视为无穷大......
  • 除此之外，我还建议您使用

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

不要使用(low+high)/2. 这可能导致总和超过整数的限制，并导致负值。您的代码可能失败的另一个原因。

于 2013-08-08T05:01:39.873 回答
2

使用正常的二进制搜索，但如果arrC[high] < arrC[low]，则将arrC[high]其视为无穷大以考虑回绕。为此，只需更改行：

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

至：

if (arrC[high] < arrC[low] || arrC[mid] > arrC[high])
于 2013-08-08T03:26:11.003 回答
-2 
#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;
}

注意：如果排序数据中包含相同的值，则不可能简单地将搜索范围减半，因为无法轻松确定要搜索的方向。但是，如果不包括相同的值，则有可能。

于 2013-08-08T09:59:53.607 回答