4

だから私は、キーがあるインデックスを返すコードを書きたいと思っています。私は何が欠けていますか？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;
}
4

5 に答える 5

3

私は実質的に同じ問題を抱えていたので、この汎用コードを書きました (std とは異なる名前空間を使用したいかもしれません ;) ) 以下のコードは、イテレータを、シーケンス内で val 以下の最大の要素に返します。 . [first ... last) での O(1) ランダム アクセスを想定して、N = std::difference(first, last) に対して O(N log N) 時間を使用します。

#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 および arrays、またはランダム アクセスを許可する任意のシーケンスを受け入れます。仮定 (前提条件を読む) は、std::binary_search に必要なように、val >= *first であり、値 [first, last) がソートされていることです。

私が使用したバグや不正行為について自由に言及してください。

于 2014-06-23T12:49:54.763 に答える
1 
int binary_srch_ret_index(ll inp[MAXSIZE], ll e, int low, int high) {

    if (low > high) {
        return -1;
    }

    int mid = (low + high) / 2;

    if (e == inp[mid]) {
        return mid;
    }

    if (e < inp[mid]) {
        return binary_srch(inp, e, low, mid - 1);
    } else {
        return binary_srch(inp, e, mid + 1, high);
    }
}
于 2014-07-09T10:09:46.487 に答える
0

文字を検索し、buf 内の文字がソートされていると想定しました。

文字列を検索する場合は、文字列一致パターン アルゴリズムを使用します。( http://en.wikipedia.org/wiki/String_searching_algorithm )

順序付き配列内の文字または数字を検索する場合は、これを参照してください: http://www.programmingsimplified.com/c/source-code/c-program-binary-search

于 2013-10-26T07:12:54.473 に答える
0

二分探索では、参照型ではなく値型検索を行うことができます。文字列配列で文字列を検索する場合は、複雑なプログラムを作成するか、has テーブルを使用する必要があります

于 2013-10-26T07:21:11.530 に答える
0

これはうまくいくようです：

#include <iostream>
#include <cassert>

int binarySearch(int buf[], int key, int min, int max);

    int main()
{
    int data[] = {1,2,4,6,7,9};

    for(int i=0; i<6; i++)
    {
        int result = binarySearch(data, data[i], 0, 5);
        assert(result == i);
    }

    assert(binarySearch(data, 3, 0, 5) == 1);
    assert(binarySearch(data, 5, 0, 5) == 2);
    assert(binarySearch(data, 8, 0, 5) == 4);
    assert(binarySearch(data, 10, 0, 5) == 5);

    return 0;
}



int binarySearch(int buf[], int 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 std::min(min, max);
}
于 2013-10-26T07:25:41.640 に答える