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

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

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

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

C++

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

Q&A

解決済

2回答

548閲覧

n x 4の二次元vectorを二分探索するプログラムがうまく動かない

abuk

総合スコア20

アルゴリズム

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

C++

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

0グッド

0クリップ

投稿2018/10/10 18:13

重複のない4次元のint型を格納する、要素の値が必ず2桁以下となっているvectorを二分探索しようとして、5つ目の要素として新たに
vec[i][4] = vec[i][0]*1000000 + vec[i][1]*10000 + vec[i][2]*100 + vec[i][3]
5つ目の要素を追加して、この値でソートすることで二分探索をしようとしたのですが、同じvectorが存在するのにも関わらず存在しないという結果が帰ってくることがあります。
二分探索の関数は下のようになっています。

c++

1 2 int vector_finder(std::vector<std::vector<int>> array, std::vector<int> new_v) 3 { 4 if ((int)array.size() == 0) return -1; 5 6 int l = 0; 7 int r = (int)array.size() - 1; 8 while (l < r) 9 { 10 11 int m = (l + r) / 2; 12 13 if (array[m][4] < new_v[4]) l = m + 1; 14 else if (array[m][4] > new_v[4]) r = m - 1; 15 else return m; 16 17 } 18 19 return -1; 20 21 }

二次元配列に新たに要素を追加する時は以下の関数を使って、

c++

1 int Insert_index(std::vector<std::vector<int>> array, std::vector<int> new_v) 2 { 3 4 5 if ((int)array.size() == 0) return 0; 6 7 int l = 0; 8 int r = (int)array.size() - 1; 9 while (l < r) 10 { 11 12 int m = (l + r) / 2; 13 14 if (array[m][4] < new_v[4]) l = m + 1; 15 else if (array[m][4] > new_v[4]) r = m - 1; 16 else return m; 17 18 } 19 20 21 22 if (array[l][4] > new_v[4]) return l; 23 else if(array[l][4] < new_v[4]) return l+1; 24 else return l; 25 } 26

二次元配列に下のように要素を加えています。

c++

1new_v = std::vector<int>{10,11,9,8,0} 2new_v[4] = new_v[0]*1000000 + new_v[1]*10000 + new_v[2]*100 + new_v[3]; 3insert_index = Insert_index(array,new_v); 4array.insert(array.begin() + insert_index, new_v); 5

arrayを表示しても、確かに5要素目でソートはされているのですが、何故か二分探索時にarrayに同じ要素が存在するにも関わらず存在しないと-1が返ってくる場合があります。これは何が原因なのでしょうか?
教えてくださるとありがたいです。

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

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

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

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

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

guest

回答2

0

ベストアンサー

例えば、目的の要素が4番目にあり、二分探索のある段階でl=3,r=4になったとします。
m=(3+4)/2=3で、lが1増え4になります。この次でl<rを満たさないので、4番目がチェックされることなくループを抜けてしまいます。
このため、lとrのインデックスが一致するときまでチェックが必要です。whileのループの条件をl<=rに変更してください。

投稿2018/10/11 00:13

swordone

総合スコア20649

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

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

0

vector_finder も Insert_index も不要、二分検索ならlower_bound/upper_boundで一発OKすよ。

C++

1#include <iostream> 2#include <iomanip> 3#include <random> 4#include <vector> 5#include <algorithm> 6 7int main() { 8 // 比較のためのキー値 9 auto key = [](const std::vector<int>& vec) { 10 return vec[0]*1000000 + vec[1]*10000 + vec[2]*100 + vec[3]; 11 }; 12 // vector<int> の比較 13 auto compare = [&](const std::vector<int>& x, const std::vector<int>& y) { 14 return key(x) < key(y); 15 }; 16 std::mt19937 gen; 17 std::uniform_int_distribution<int> dist(0,99); 18 19 std::vector<std::vector<int>> array; 20 21 for ( int i = 0; i < 20; ++i ) { 22 // 乱数でvector<int> を作り 23 std::vector<int> item({dist(gen), dist(gen), dist(gen), dist(gen)}); 24 // 挿入位置を見つけて(vector_finderに相当) 25 auto where = std::upper_bound(array.begin(), array.end(), item, compare); 26 // そこに挿入 27 array.insert(where, item); 28 } 29 30 // 結果を確認 31 for ( const auto& item : array ) { 32 std::cout << std::setw(3) << item[0] 33 << std::setw(3) << item[1] 34 << std::setw(3) << item[2] 35 << std::setw(3) << item[3] 36 << " : " << std::setw(8) << key(item) << std::endl; 37 } 38} 39
実行結果: 1 73 25 42 : 1732542 4 91 29 85 : 4912985 7 2 58 93 : 7025893 9 9 43 39 : 9094339 9 79 91 26 : 9799126 9 80 88 8 : 9808808 12 2 34 85 : 12023485 16 27 34 6 : 16273406 19 4 97 6 : 19049706 29 18 26 95 : 29182695 39 61 26 8 : 39612608 40 26 39 20 : 40263920 44 6 95 20 : 44069520 46 26 36 53 : 46263653 52 50 12 52 : 52501252 53 93 87 28 : 53938728 60 6 22 86 : 60062286 60 71 12 9 : 60711209 97 76 45 34 : 97764534 98 3 35 65 : 98033565

投稿2018/10/12 15:46

編集2018/10/12 15:55
episteme

総合スコア16614

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

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問