首页 文章

找到循环排序数组中的最小元素[重复]

提问于
浏览 次
5

这个问题在这里已有答案：

我已经尝试了以下代码来找出循环排序数组中的最小元素 . 但是当low = 1和high = 2时它会失败，因为mid总是1而且[mid] = a [1]总是大于a [high] .

我想在这里使用二进制搜索来找到解决方案 .

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

3 回答

  • 3

    使用普通二进制搜索，但如果 arrC[high] < arrC[low] ，则将 arrC[high] 视为无穷大以考虑环绕 . 要做到这一点，只需更改行：

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

    至：

    if (arrC[high] < arrC[low] || arrC[mid] > arrC[high])
    回复于
  • 2

    您的代码有2个问题

    • 正如Paulpro所指出的那样......将arrC [high]视为无穷大......

    • 除此之外，我还建议你使用

    mid = low（high-low）/ 2;

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

    回复于
  • -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;
}

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

    回复于

相关问题