找到循环排序数组中的最小元素

发布时间：2020-12-16 05:05:51 所属栏目：百科来源：网络整理

导读：参见英文答案 Need an algorithm for a special array (linear field)3个我已经尝试了以下代码来找出循环排序数组中的最小元素.但是当low = 1和high = 2时它会失败,因为mid总是1而且[mid] = a [1]总是大于a [high]. 我试图在这里使用二进制搜索来找到解决方

参见英文答案 > Need an algorithm for a special array (linear field)3个
我已经尝试了以下代码来找出循环排序数组中的最小元素.但是当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]);

解决方法

使用普通的二进制搜索,但是如果arrC [high]< arrC [low],将arrC [high]视为无穷大来解释环绕.要做到这一点,只需更改行：

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

至：

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!