我在C中实现了二进制搜索，如下所示，但是当我传递排序数组中不可用的元素时，代码进入无限循环，因为midelement重复计算相同的值（中间元素为4，然后开始索引变为5（元素查找〉输入数组[中间元素]），结束索引为4，因此，在循环的第9次迭代之后，再次返回中间元素为4），有人能找到我如何改进这个逻辑吗？
#define MAX_NUM_INPUT (358U)
uint16 InputArray[MAX_NUM_INPUT] = {0x0103, 0x0104, 0x0109, 0x010A, 0x0133, 0x0180, 0x181, 0x183,.....upto 358 elements};
int main()
{
boolean elmntFound = 0;
uint16 elmntTofnd = 0x0134;
elmntFound = SearchPassedElement(0, MAX_NUM_INPUT, elmntTofnd);
if(elmntFound == 0)
{
printf("elementfound");
}
else
{
printf("elementNOTfound");
}
}
static boolean SearchPassedElement (uint16 FrstElmntIdx,uint16 LstElmntIdx, uint16 ElmntToFind)
{
boolean ReturnValue = 1;
uint16 startIdx = FrstElmntIdx;
uint16 endIdx = LstElmntIdx;
uint16 loc_midElmntIdx;
boolean OperationStatus = FALSE;
if(LstElmntIdx >= FrstElmntIdx)
{
while (OperationStatus == FALSE)
{
loc_midElmntIdx = (startIdx + endIdx) / 2U ;
if (ElmntToFind == InputArray[loc_midElmntIdx])
{
OperationStatus = TRUE;
ReturnValue = 0 ;
}
else if (ElmntToFind > InputArray[loc_midElmntIdx])
{
/* if entire array was already checked*/
if (startIdx == endIdx)
{
OperationStatus = TRUE;
ReturnValue = 1 ;
}
else /* othewise, */
{
startIdx = loc_midElmntIdx + 1U;
}
}
else
{
/* if entire array was already checked*/
if (startIdx == endIdx)
{
OperationStatus = TRUE;
ReturnValue = 1 ;
}
else /* othewise, */
{
endIdx = loc_midElmIdx - 1U ;
}
}
}
}
else
{
loopCntr = 0;
/* Incorrect input arguments */
ReturnValue = 1;
}
return ReturnValue;
}我发现了一个逻辑，如果midelemnt返回相同的值超过3次，lop将被中断，并评估相同的值。
static boolean SearchPassedElement (uint16 FrstElmntIdx,uint16 LstElmntIdx, uint16 ElmntToFind)
{
boolean ReturnValue = 1;
uint16 startIdx = FrstElmntIdx;
uint16 endIdx = LstElmntIdx;
uint16 loc_midElmntIdx;
boolean OperationStatus = FALSE;
uint16 prev_loc_midElmIdx = 0;
uint16 is_midElmIdxSame_count = 0;
if(LstElmntIdx >= FrstElmntIdx)
{
while (OperationStatus == FALSE)
{
loc_midElmntIdx = (startIdx + endIdx) / 2U ;
if (ElmntToFind == InputArray[loc_midElmntIdx])
{
OperationStatus = TRUE;
ReturnValue = 0 ;
}
else if (ElmntToFind > InputArray[loc_midElmntIdx])
{
/* if entire array was already checked*/
if (startIdx == endIdx)
{
OperationStatus = TRUE;
ReturnValue = 1 ;
}
else /* othewise, */
{
startIdx = loc_midElmntIdx + 1U;
}
}
else
{
/* if entire array was already checked*/
if (startIdx == endIdx)
{
OperationStatus = TRUE;
ReturnValue = 1 ;
}
else /* othewise, */
{
endIdx = loc_midElmIdx - 1U ;
}
}
if(prev_loc_midElmIdx != loc_midElmIdx)
{
prev_loc_midElmIdx = loc_midElmIdx;
}
else
{
is_midElmIdxSame_count++;
/*as the divisor is 2 the same value can't return more that 2 times, hence if the same value is return more than
* 2 times the loop should be braked
*/
if(is_midElmIdxSame_count == 3)
{
elmntNotFnd = 3;
/* Stop operation and return failure*/
OperationStatus = TRUE;
ReturnValue = 1 ;
}
}
}
}
else
{
loopCntr = 0;
/* Incorrect input arguments */
ReturnValue = 1;
}
return ReturnValue;
}
1条答案
按热度按时间s8vozzvw1#
在C语言中没有
boolean类型，你必须使用#include <stdbool.h>才能使用bool类型，对于uint16也是一样，你必须使用#include <stdint.h>和uint16_t。而且你的代码非常复杂。你不必要地使用很多变量来完成一件简单的事情。
下面是一个更紧凑的版本：
如果找到元素，则返回
true，否则返回false。示例：
x一个一个一个一个x一个一个二个x
需要注意的几点：
size_t是索引数组的适当类型。const（即只读）。