This question already has answers here:
Need an algorithm for a special array (linear field)
(3个答案)
7年前关闭。
我尝试了以下代码来找出循环排序数组中的最小元素。但是,当low = 1和high = 2时,它会失败,因为中值始终为1,并且a [mid] = a [1]始终大于a [high]。
我试图在这里使用二进制搜索来找到解决方案。
至:
(3个答案)
7年前关闭。
我尝试了以下代码来找出循环排序数组中的最小元素。但是,当low = 1和high = 2时,它会失败,因为中值始终为1,并且a [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])
关于c - 在循环排序数组中找到最小元素,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/18117350/
10-12 19:54