void binary_search_vec(std::vector<int> a, int finder) {
auto full_beg = a.begin();
auto beg = a.begin();
auto end = a.end();
auto mid = beg + (end - beg) / 2;
while (*mid != finder && mid != end) {
if (finder > *mid) {
beg = mid + 1;
}
else { //(*mid > finder)
end = mid;
}
mid = beg + (end - beg) / 2;
if (finder == *mid) { // Here is the problem leading to undefined behavior. I am negating the condition in the While Loop. Credit to Bob___ for the fix. And thank you to the community.
std::cout << "Num found: " << finder << " at position: " << std::distance(full_beg, mid) <<
std::endl;
break;
}
}
}
编辑：有问题的代码来自C++初级读本第5版。有问题的二进制搜索根本不会返回找到的num。我不明白为什么。与其他用户逐行比较。他们的工作我没有。
来自另一个用户的此代码有效。我不明白其中的区别第二次编辑：@Bob___修复代码：
auto full_beg = a.begin();
auto beg = a.begin();
auto end = a.end();
auto mid = beg + (end - beg) / 2;
while (*mid != finder && mid != end) {
if (finder > * mid) {
beg = mid + 1;
}
else { //(*mid > finder)
end = mid;
}
mid = beg + (end - beg) / 2;
}
if (finder == *mid) {
std::cout << "Num found: " << finder << " at position Index: " << std::distance(full_beg, mid) << std::endl;
}
else std::cout << "Not Found!" << std::endl;
}
将最后一个if分支移出while循环并删除break语句，否则如果finder与mid相同，它将不起作用。
以下代码有效：
#include <iostream>
#include <vector>
void binary_search_vec(std::vector<int> a, int finder) {
auto full_beg = a.begin();
auto beg = a.begin();
auto end = a.end();
auto mid = beg + (end - beg) / 2;
std::cout << "MID AT THE BEGINNING: " << *mid << std::endl;
while (mid != end && *mid != finder) {
if (finder > *mid) {
std::cout << "Finder > mid" << std::endl;
beg = mid + 1;
}
else { //(*mid > finder)
std::cout << "Finder > mid" << std::endl;
end = mid;
}
mid = beg + (end - beg) / 2;
std::cout << "Setting mid to " << *mid << std::endl;
}
if (finder == *mid) {
std::cout << "Num found: " << finder << " at position: " << std::distance(full_beg, mid) << std::endl;
}
}
int main() {
std::cout << "Hello World!n";
std::vector<int> v = std::vector<int>();
v.push_back(0);
v.push_back(1);
v.push_back(2);
v.push_back(3);
binary_search_vec(v, 1);
}
使用您的函数，以前的代码在finder = 2时不起作用。
另请查看@Bob__的评论：这段时间内的条件评估顺序极其重要！
以下是修复和更新的代码。由Bob___ 提供
void binary_search_vec(std:：vector a，int finder(｛
auto full_beg = a.begin();
auto beg = a.begin();
auto end = a.end();
auto mid = beg + (end - beg) / 2;
while (*mid != finder && mid != end) {
if (finder > * mid) {
beg = mid + 1;
}
else { //(*mid > finder)
end = mid;
}
mid = beg + (end - beg) / 2;
}
if (finder == *mid) {
std::cout << "Num found: " << finder << " at position Index: " << std::distance(full_beg, mid) << std::endl;
}
else std::cout << "Not Found!" << std::endl;
}