使用二进制搜索已排序向量

Question

我一直在试图让使用二进制搜索在一个向量元素的位置，找到没有排序的向量元素而已，没有循环，没有什么，从库algorithm只是二进制搜索功能。

由于二进制搜索函数仅适用于已排序的容器类型，我不知道如何获取原始向量的搜索元素的位置，因为一旦向量排序，搜索到的元素的位置可能不会与在原始矢量中。

我做的代码工作，std::find，但我的主要目标是，只有二进制搜索功能做这个工作。

代码：

#include <iostream> 
#include <vector> 
#include <algorithm> 

int main() 
{ 
    std::vector<int> v {1, 10, 100, -11, -112, -17, 44, -99, 99, 558}; 

    std::vector<int> sorted = v; 
    std::sort(sorted.begin(), sorted.end()); 

    std::cout << "Enter a number: "; 
    int number; 
    std::cin >> number; 

    if(std::binary_search(sorted.begin(), sorted.end(), number) == false) 
    { 
     std::cout << "There is no entered number."; 
    } 
    else 
    { 
     std::cout << "Number is located on position: "; 
     std::cout << std::find(v.begin(), v.end(), number) - v.begin(); 
    } 
    return 0; 
} 

输出的例子：

1°

Enter a number: 99 
Number is located on position: 8 

2°

Enter a number: -546 
There is no entered number. 

所以，如果有人可以帮助我做二进制这项工作功能，而不是std::find或者给我几点想法，我会很感激。

谢谢:)

Answer 1

由于NathanOliver指出，这是不可能做到的非排序的数据的二进制搜索。

如果你的向量保证每个数字至多有一次，而你不想改变顺序，你可以保留一张地图，以保持你的向量包含的每个int的索引。

map<int, size_t> idxMap; 

你也使用std::find_if这将做一个线性搜索

int valueToFind; 
vector<int>::const_iterator it = std::find_if(v.begin(), v.end(), [valueToFind](int entry) { return entry == valueToFind;)}; 

我会推荐的第一选择，如果你没有在内存方面的限制，你想要做搜索的显著数。

Answer 2

如果你想要做一个二进制搜索，并有结果指回到原来的排序的数组 - 你需要做的指数排序和搜索 - 而不是分类和对数组的副本检索，你在一组索引中操作原始数组。例如：

std::vector<int> v {1, 10, 100, -11, -112, -17, 44, -99, 99, 558}; 

std::vector<int> sort_indexes(v.size()); 
for (size_t i = 0; i < v.size(); ++i) 
    sort_indexes[i] = i; 

std::sort(sort_indexes.begin(), sort_indexes.end(), 
      [&v](int a, int b)->bool { return v[a] < v[b]; }); 

std::cout << "Enter a number: "; 
int number; 
std::cin >> number; 

auto found = std::lower_bound(sort_indexes.begin(), sort_indexes.end(), number, 
           [&v](int a, int b)->bool { return v[a] < b; }); 

if (found == sort_indexes.end() || v[*found] > number) { 
    std::cout << "There is no entered number." << std::endl; 
} else { 
    std::cout << "Number is located on position: " << *found << std::endl; 
}