C++字符串数组二分查找异常：返回-1却输出不存在的字符串

你遇到的是数组越界访问导致的未定义行为，虽然当前结果看似有规律，但本质是内存访问违规，完全不可靠。

具体原因 #

当binary_search返回-1时，你执行了names[index]也就是names[-1]——这属于访问数组首元素之前的内存区域，C++标准完全禁止这种操作，属于未定义行为范畴。

之所以每次都输出"ali2"，是当前栈内存布局的偶然结果：

• std::string在处理短字符串时通常会采用小字符串优化，直接在对象内部存储字符串内容；
• 你传入的目标字符串"ali2"在函数调用过程中曾被存储在栈上的某个位置，而数组越界访问刚好命中了这块内存，当以std::string的格式解析时，就显示出了"ali2"。

但务必注意：这种结果是巧合，更换编译器、编译参数或运行环境后，可能会出现乱码、程序崩溃，甚至执行完全无关的代码。

修复方案 #

在输出前先判断索引是否有效，仅当索引合法时才访问数组元素：

int main(int argc, char **argv)
{
  string names[] = {
    "ali",
    "arsham",
    "bahman",
    "bahram",
    "bizhan",
    "darioush",
    "erfan",
    "parsa",
    "setayesh"
  };
  int index = binary_search(names, ARR_LENGTH(names), "ali2");
  cout << "given index is : " << index << endl;
  if (index != -1) {
    cout << "founded name is : " << names[index] << endl;
  } else {
    cout << "name not found" << endl;
  }
  return 0;
}

另外，你的二分查找代码存在风格问题：混合使用std::string的==运算符和C语言的strcmp，建议直接用std::string的比较运算符替代，代码更简洁安全，比如将strcmp(target.c_str(), item.c_str()) < 0改为target < item。

内容的提问来源于stack exchange，提问作者p.mahmoudy