質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

2回答

557閲覧

自作の二分探索のバグが取れない

退会済みユーザー

退会済みユーザー

総合スコア0

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2020/04/24 02:41

イテレータを返す二分探索を書いているのですが、mid, distなどの加減をどう変えてみても正しく判定されないものがいくつか出てきます。
std::distanceの呼び出しを1度で抑えるのが目的なので、できればwhile内の条件分岐部分を直す方法が知りたいです。
どうすれば良いでしょうか?

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

#include <functional> #include <iostream> #include <vector> typedef std::vector<int>::const_iterator Iterator; template<class Compare> Iterator BinarySearch(Iterator begin, Iterator end, Compare comp) { auto dist = std::distance(begin, end); auto it = begin; auto not_found = end; while (dist > 0) { auto mid = it; dist /= 2; std::advance(mid, dist); auto comp_result = comp(*mid); if (comp_result == 0) { return mid; } else if (comp_result < 0) { // *midが探索対象より小さい it = ++mid; --dist; } else { // *midが探索対象より大きい end = --mid; --dist; } } return not_found; } int main() { std::vector list1{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; std::vector list2{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}; std::vector test_numbers{-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}; auto bin_search_wrapper = [](std::vector<int> &list, int target) { return BinarySearch(std::begin(list), std::end(list), [target](const int &cur) { if (cur < target) { return -1; } else if (cur == target) { return 0; } return 1; }); }; std::cout << "Test BinarySearch()\n" << "list1{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}\n"; for (const auto &n : test_numbers) { if (auto it = bin_search_wrapper(list1, n); it != std::end(list1)) { std::cout << n << ": found" << "\n"; } else { std::cout << n << ": not found" << "\n"; } } std::cout << "\nlist2{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}\n"; for (const auto &n : test_numbers) { if (auto it = bin_search_wrapper(list2, n); it != std::end(list2)) { std::cout << n << ": found" << "\n"; } else { std::cout << n << ": not found" << "\n"; } } }

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

episteme

2020/04/24 04:57

これ、12223 から 2 を探すと 真ん中の2 をみつけますよね。 ひとつみつけたらそこで検索終了していいんですか? 最も左寄り(or右寄り)の2 をみつけなくていいんですか?
退会済みユーザー

退会済みユーザー

2020/04/24 05:52

そこまで考えていませんでした。確かに今のままだと実用的ではありませんね。 左寄り(あるいは右寄り)を得るには、どういう操作を追加すればよいのでしょうか?
episteme

2020/04/24 12:33

「一致しても二分法を止めない」じゃねぇの?
guest

回答2

0

これでもよいようですが。

C++

1template<class Compare> 2Iterator BinarySearch(Iterator begin, Iterator end, Compare comp) { 3 auto not_found = end; 4 int dist; 5 6 while ((dist = end - begin)) > 0) { 7 auto mid = begin + dist / 2; 8 auto comp_result = comp(*mid); 9 10 if (comp_result < 0) // *midが探索対象より小さい 11 begin = mid + 1; 12 else if (comp_result > 0) // *midが探索対象より大きい 13 end = mid; 14 else 15 return mid; 16 } 17 return not_found; 18}

投稿2020/04/24 05:26

編集2020/04/24 07:34
kazuma-s

総合スコア8224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2020/04/24 08:23

簡潔で良いですね。 C++ではwhile()内で代入ができるとは知りませんでした。
guest

0

ベストアンサー

c++

1 while (dist > 0) { 2 auto mid = it; 3 auto be_even = dist % 2 == 0; 4 dist /= 2; 5 std::advance(mid, dist); 6 auto comp_result = comp(*mid); 7 8 if (comp_result == 0) { 9 return mid; 10 } else if (comp_result < 0) { // *midが探索対象より小さい 11 it = ++mid; 12 if(be_even) --dist; 13 } else { // *midが探索対象より大きい 14 end = mid; 15 } 16 }

投稿2020/04/24 03:42

asm

総合スコア15147

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問