重複のない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が返ってくる場合があります。これは何が原因なのでしょうか?
教えてくださるとありがたいです。
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。