含重复元素的二分查找返回最小索引代码出现Segmentation fault求助

你的代码出现段错误（Segmentation fault）主要有以下几个核心问题：

1. 中间索引mid计算错误 #

int mid = right - left / 2; 中除法运算优先级高于减法，实际计算的是 right - (left/2)，这会导致mid值严重偏离正确范围，访问数组时直接越界，触发段错误。正确的mid计算应该是 left + (right - left)/2（避免整数溢出）或者 (left + right)/2。

2. 递归与循环混合，逻辑混乱 #

代码同时使用while循环和递归调用，导致终止条件失控，容易出现无限递归或者错误的数组访问。比如找到匹配元素时直接递归，但没有正确处理递归终止逻辑，可能导致重复进入递归，最终引发栈溢出或越界。

3. 初始终止条件错误 #

if (right - left == 0) return right; 这个判断没有检查当前元素是否等于目标x，就算目标不存在也会返回索引，导致结果错误，同时干扰后续循环逻辑。

修正后的代码（纯循环实现，更稳定） #

int binary_search(const vector<int> &a, int left, int right, int x)
{
    int result = -1;
    while (right >= left)
    {
        int mid = left + (right - left) / 2; // 正确计算mid，避免溢出
        if (a[mid] == x)
        {
            result = mid; // 记录当前索引，继续向左搜索更小的匹配位置
            right = mid - 1;
        }
        else if (a[mid] > x)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    return result;
}

int main()
{
    int n;
    std::cin >> n;
    vector<int> a(n);
    for (size_t i = 0; i < a.size(); i++)
    {
        std::cin >> a[i];
    }
    int m;
    std::cin >> m;
    vector<int> b(m);
    for (int i = 0; i < m; ++i)
    {
        std::cin >> b[i];
    }
    for (int i = 0; i < m; ++i)
    {
        std::cout << binary_search(a, 0, (int)a.size() - 1, b[i]) << ' ';
    }
}

代码说明 #

• 用result变量记录当前找到的目标索引，匹配到元素时不立即返回，而是继续向左收缩搜索范围（right = mid - 1），确保找到最小的索引。
• 修正mid的计算方式，彻底避免数组越界和整数溢出问题。
• 移除混乱的递归逻辑，改用纯循环实现，逻辑更清晰，同时避免递归栈溢出的风险。

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