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

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; 
}