c++ - BinarySearch 返回它所属位置的索引

Question

所以我想写一个代码来返回键所在的索引，或者如果它不存在，它应该在哪里。我错过了什么？ min 为 0，max 为 size - 1，buf 已排序

int binarySearch(string buf[], string key, int min, int max){

int mid;
while (max >= min){
    mid = (min + max) / 2;

    if (buf[mid] < key)
        min = mid + 1;
    else if (buf[mid] > key)
        max = mid - 1;

    else
        return mid;

}
return min;
}

Answer 1

我实际上遇到了同样的问题，所以我写了这个通用代码(也许你可能想使用与 std 不同的命名空间；))下面的代码返回一个迭代器到序列中小于或的最大元素等于值。它使用 O(N log N) 时间 N = std::difference(first, last)，假设 O(1) 随机访问 [first ... last]。

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

namespace std {

template<class RandomIt, class T>
RandomIt binary_locate(RandomIt first, RandomIt last, const T& val) {
  if(val == *first) return first;
  auto d = std::distance(first, last);  
  if(d==1) return first;
  auto center = (first + (d/2));
  if(val < *center) return binary_locate(first, center, val);
  return binary_locate(center, last, val);
}  

}

int main() {
    std::vector<double> values = {0, 0.5, 1, 5, 7.5, 10, 12.5};
    std::vector<double> tests = {0, 0.4, 0.5, 3, 7.5, 11.5, 12.5, 13};
    for(double d : tests) {
        auto it = std::binary_locate(values.begin(), values.end(), d);
        std::cout << "found " << d << " right after index " << std::distance(values.begin(), it) << " which has value " << *it << std::endl;
    }
    return 0;
}

来源:http://ideone.com/X9RsFx

代码非常通用，它接受 std::vectors、std::arrays 和数组，或任何允许随机访问的序列。假设(读取前提条件)是 val >= *first 并且值 [first, last) 已排序，如 std::binary_search 所需。

请随意提及我使用过的错误或不当行为。