C++ 字符串数组二分查找

Question

string Haystack[] =  { "Alabama", "Alaska", "American Samoa", "Arizona", "Arkansas", "California", "Colorado", "Connecticut", "Delaware", "District of Columbia",
                 "Florida", "Georgia", "Guam", "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas", "Kentucky", 
                 "Louisiana", "Maine", "Maryland", "Massachusetts", "Michigan", "Minnesota", "Mississippi", "Missouri", "Montana", "Nebraska", 
                 "Nevada", "New Hampshire", "New Jersey", "New Mexico", "New York", "North Carolina", "North Dakota", "Northern Mariana Islands", "Ohio", "Oklahoma",
                 "Oregon", "Pennsylvania", "Puerto Rico",  "Rhode Island", "South Carolina", "South Dakota", "Tennessee", "Texas", "US Virgin Islands", "Utah",
                 "Vermont", "Virginia", "Washington", "West Virginia", "Wisconsin", "Wyoming"};

 string Needle = "Virginia";

 if(std::binary_search(Haystack, Haystack+56, Needle))
      cout<<"Found";

如果我还想在字符串数组中找到针的位置，是否有一种“简单”的方法可以找到？

Answer 1

来自SGI docs :

Note that this is not necessarily the information you are interested in! Usually, if you're testing whether an element is present in a range, you'd like to know where it is (if it's present), or where it should be inserted (if it's not present). The functions lower_bound, upper_bound, and equal_range provide this information.

我认为这组接口(interface)背后的原因是 binary_search 并没有真正表明它会返回匹配范围的开始(假设有匹配)还是结束范围，您可能需要一个或另一个，具体取决于您是要对容器中已有的数据执行某些操作还是添加新项目(可能到匹配范围的末尾)。或者您可能想将整个范围传递给其他东西。因此，有各种或多或少特定的接口(interface)来执行二进制搜索。

不幸的是，如果您在想“我需要一个二进制搜索例程”，那么您不太可能找到其他的。