为何结合线性搜索与单次拆分二分搜索的插值搜索无法返回向量最后元素的对应索引？

你的代码遇到的核心问题有两个：输入循环的逻辑错误导致最后一个元素没有被添加到向量中，以及**valIndex变量未初始化带来的未定义行为**。这两个问题共同导致了当目标是“原本应该是最后一个元素”时，程序返回错误结果——因为这个元素根本没被加入列表，valIndex输出的是未初始化的垃圾值。

一、输入循环的致命错误 #

你用来读取列表的while循环条件存在逻辑缺陷：

while (cin >> listVal && cin.peek() != '\n') {
 orderedList.push_back(listVal);
};

当用户输入最后一个元素后按下回车，cin >> listVal会成功读取最后一个元素，但此时cin.peek()会检测到换行符'\n'，导致循环条件不成立，最后一个元素不会被添加到orderedList中。比如你输入1 2 3 4并回车，向量里只会有[1,2,3]，你要搜索4时，向量里根本没有这个值，自然返回错误。

修复这个输入循环的正确方式是，先读取元素，再判断是否终止：

// 读取有序列表，直到输入换行
while (cin >> listVal) {
    orderedList.push_back(listVal);
    // 如果下一个字符是换行，终止循环
    if (cin.peek() == '\n') {
        break;
    }
}

二、未初始化变量valIndex的问题 #

你的valIndex是局部int变量，没有初始化，默认会是内存中的随机垃圾值。如果目标元素不存在（或因为输入问题没被加入列表），程序会输出这个垃圾值，导致结果不符合预期。

修复方式是初始化valIndex为一个特殊值（比如-1），用来表示“未找到目标元素”，这样无论是否找到，都能输出明确的结果：

int valIndex = -1; // 初始化表示未找到状态

三、修复后的线性搜索代码 #

#include <iostream>
#include <vector>
using namespace std;

int main () {
    int listVal;
    int searchedVal;
    int valIndex = -1; // 初始化未找到状态
    vector<int> orderedList;

    cout << "Enter the ordered list: " << endl;
    // 修复输入循环，确保最后一个元素被加入
    while (cin >> listVal) {
        orderedList.push_back(listVal);
        if (cin.peek() == '\n') {
            break;
        }
    };

    cout << "Enter the desired key: " << endl;
    cin >> searchedVal;

    // Linear Search
    for (int i = 0; i < orderedList.size(); i++) {
        int currVal = orderedList.at(i);
        if (currVal == searchedVal) {
            valIndex = i;
            break; // 找到后直接终止循环，提升效率
        }
    };

    if (valIndex != -1) {
        cout << "The index of the key is: " << valIndex << endl;
    } else {
        cout << "Key not found in the list." << endl;
    }

    return 0;
};

四、修复后的二分搜索变体代码 #

你的二分搜索逻辑是“一次拆分后线性搜索”，除了修复输入和变量初始化，还可以优化右半部分的起始索引（中间元素已判断过不等于目标，无需重复遍历）：

#include <iostream>
#include <vector>
using namespace std;

int main () {
    int listVal;
    int searchedVal;
    int valIndex = -1; // 初始化未找到状态
    vector<int> orderedList;

    cout << "Enter the ordered list: " << endl;
    // 修复输入循环
    while (cin >> listVal) {
        orderedList.push_back(listVal);
        if (cin.peek() == '\n') {
            break;
        }
    };

    cout << "Enter the desired key: " << endl;
    cin >> searchedVal;

    if (orderedList.empty()) {
        cout << "The list is empty." << endl;
        return 0;
    }

    // Binary Search + Linear Variant
    int mid = orderedList.size() / 2;
    if (searchedVal == orderedList.at(mid)) {
        valIndex = mid;
    } else if (searchedVal < orderedList.at(mid)) {
        // 搜索左半部分，从0到mid-1
        for (int i = 0; i < mid; i++) {
            if (orderedList.at(i) == searchedVal) {
                valIndex = i;
                break;
            }
        };
    } else {
        // 搜索右半部分，从mid+1到末尾
        for (int j = mid + 1; j < orderedList.size(); j++) {
            if (orderedList.at(j) == searchedVal) {
                valIndex = j;
                break;
            }
        };
    };

    if (valIndex != -1) {
        cout << "The index of the key is: " << valIndex << endl;
    } else {
        cout << "Key not found in the list." << endl;
    }

    return 0;
};

总结 #

修复输入循环和变量初始化后，无论是最后一个元素还是其他元素，程序都能正确返回索引或提示未找到。另外添加的空列表判断和循环终止逻辑，也让代码更健壮高效。

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