C语言二分查找未找到元素时陷入死循环的优化咨询

我用C实现了二分查找代码，但查找有序数组中不存在的元素时会陷入死循环。原因是循环多次后中间元素索引会重复计算——比如当start变为5、end为4时，计算出的中间索引仍为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 ; // 变量名拼写错误：应为loc_midElmntIdx
                }
            }
        }
    }
    else 
    {
        loopCntr = 0; // loopCntr未定义
        /* Incorrect input arguments */
        ReturnValue = 1;
    }
    return ReturnValue;
}

尝试的优化代码 #

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; // elmntNotFnd未定义
                    /* Stop operation and return failure*/
                    OperationStatus = TRUE;
                    ReturnValue   = 1 ;
                }
            }
        }
    }
    else 
    {
        loopCntr = 0; // loopCntr未定义
        /* Incorrect input arguments */
        ReturnValue = 1;
    }
    return ReturnValue;
}

改进方案 #

你的优化属于“补丁式”修复，没解决根本问题。死循环的核心原因是：当startIdx > endIdx时循环仍未终止，且此时(startIdx + endIdx)/2会因无符号整数特性计算出错误的中间索引，导致循环无法退出。以下是正确的改进方式：

1. 修正循环终止条件 #

把循环条件改为startIdx <= endIdx，当没有元素可查（startIdx > endIdx）时直接退出，无需额外状态标志。

2. 修复变量拼写错误 #

统一所有变量名（比如loc_midElmntIdx和loc_midElmIdx），避免编译错误或未定义行为。

3. 避免整数溢出 #

(startIdx + endIdx)可能超过uint16最大值（65535），改用startIdx + (endIdx - startIdx)/2计算中间索引，彻底避免溢出。

4. 简化逻辑，移除冗余变量 #

删掉OperationStatus、prev_loc_midElmIdx等冗余变量，让代码逻辑更清晰。

修正后的完整代码 #

#define MAX_NUM_INPUT     (358U)
uint16 InputArray[MAX_NUM_INPUT] = {0x0103, 0x0104, 0x0109, 0x010A, 0x0133, 0x0180, 0x181, 0x183, /* ... 剩余元素 ... */};

#include <stdio.h>
// 补充自定义boolean类型定义
typedef unsigned char boolean;

int main()
{
    boolean elmntFound = 0;
    uint16 elmntTofnd = 0x0134;
    // 修正数组索引越界问题：最大索引为MAX_NUM_INPUT-1
    elmntFound = SearchPassedElement(0, MAX_NUM_INPUT - 1, elmntTofnd);
    if(elmntFound == 0)
    {
        printf("elementfound\n");
    }
    else
    {
        printf("elementNOTfound\n");
    }
    return 0;
}

static boolean SearchPassedElement(uint16 FrstElmntIdx, uint16 LstElmntIdx, uint16 ElmntToFind)
{
    uint16 startIdx = FrstElmntIdx;
    uint16 endIdx = LstElmntIdx;

    // 输入合法性检查
    if (startIdx > endIdx)
    {
        return 1;
    }

    while (startIdx <= endIdx)
    {
        // 安全计算中间索引
        uint16 loc_midElmntIdx = startIdx + (endIdx - startIdx) / 2U;

        if (ElmntToFind == InputArray[loc_midElmntIdx])
        {
            // 找到元素，返回0（表示找到）
            return 0;
        }
        else if (ElmntToFind > InputArray[loc_midElmntIdx])
        {
            // 目标在右半部分，更新起始索引
            startIdx = loc_midElmntIdx + 1U;
        }
        else
        {
            // 目标在左半部分，更新结束索引
            endIdx = loc_midElmntIdx - 1U;
        }
    }

    // 循环结束未找到元素，返回1（表示未找到）
    return 1;
}

额外说明 #

• 原代码调用SearchPassedElement时传入MAX_NUM_INPUT会导致数组越界，修正为MAX_NUM_INPUT-1。
• 补充了boolean类型定义，确保代码可编译运行。
• 移除了所有未定义变量，消除潜在的编译错误。

内容的提问来源于stack exchange，提问作者Prk651989