標準のバイナリ検索を使用して、（並べ替え可能なプロパティに関して）並べ替えられたリスト内の単一のオブジェクトをすばやく返します。
次に、一致するすべてのリストエントリが返されるように検索を変更する必要があります。これをどのように行うのが最善ですか？
質問する
44513 次
13 に答える
27
さて、リストがソートされているので、あなたが興味を持っているすべてのエントリは連続しています。これは、二分探索によって生成されたインデックスからさかのぼって、見つかったアイテムと等しい最初のアイテムを見つける必要があることを意味します。そして最後のアイテムについても同じです。
見つかったインデックスから単純に逆方向に進むことができますが、この方法では、見つかったものと等しいアイテムが多数ある場合、ソリューションはO（n）と同じくらい遅くなる可能性があります。したがって、指数検索を使用することをお勧めします。より等しいアイテムが見つかったら、ジャンプを2倍にします。このように、検索全体はまだO（log n）です。
于 2012-08-27T15:28:04.583 に答える
24
まず、素朴な二分探索コードスニペットを思い出してみましょう。
int bin_search(int arr[], int key, int low, int high)
{
if (low > high)
return -1;
int mid = low + ((high - low) >> 1);
if (arr[mid] == key) return mid;
if (arr[mid] > key)
return bin_search(arr, key, low, mid - 1);
else
return bin_search(arr, key, mid + 1, high);
}
スキーナ教授からの引用：（s [middle] == key）return（middle）;の場合、等式テストを削除するとします。上記の実装から、失敗した検索ごとに-1ではなくlowのインデックスを返します。同等性テストがないため、すべての検索が失敗します。キーが同一の配列要素と比較されるたびに、検索は右半分に進み、最終的には右の境界で終了します。バイナリ比較の方向を逆にして検索を繰り返すと、左側の境界に移動します。各検索にはO（lgn）時間がかかるため、ブロックのサイズに関係なく、対数時間での発生をカウントできます。
したがって、lower_bound（KEY以上の最初の数値を検索）とupper_bound（KEYより大きい最初の数値を検索）を見つけるには、binary_searchを2回実行する必要があります。
int lower_bound(int arr[], int key, int low, int high)
{
if (low > high)
//return -1;
return low;
int mid = low + ((high - low) >> 1);
//if (arr[mid] == key) return mid;
//Attention here, we go left for lower_bound when meeting equal values
if (arr[mid] >= key)
return lower_bound(arr, key, low, mid - 1);
else
return lower_bound(arr, key, mid + 1, high);
}
int upper_bound(int arr[], int key, int low, int high)
{
if (low > high)
//return -1;
return low;
int mid = low + ((high - low) >> 1);
//if (arr[mid] == key) return mid;
//Attention here, we go right for upper_bound when meeting equal values
if (arr[mid] > key)
return upper_bound(arr, key, low, mid - 1);
else
return upper_bound(arr, key, mid + 1, high);
}
お役に立てば幸いです:)
于 2014-09-22T03:06:34.877 に答える
7
私があなたの質問に従っている場合、比較のために、のように見えるオブジェクトのリストがあります{1,2,2,3,4,5,5,5,6,7,8,8,9}。通常の5の検索では、5と比較されるオブジェクトの1つがヒットしますが、それらすべてを取得したいのですが、そうですか？
その場合、一致する要素に到達すると、一致が停止するまで左を検索し、一致が停止するまで（最初の一致から）再び右を検索する標準の二分探索をお勧めします。
使用しているデータ構造が、同じものと比較する要素を上書きしないように注意してください。
または、その位置にあるバケットと比較できる要素を格納する構造を使用することを検討してください。
于 2012-08-27T15:24:27.367 に答える
3
2つのバイナリ検索を実行します。1つは値を比較する最初の要素（C ++用語ではlower_bound）を検索し、もう1つは値を比較する最初の要素（C ++用語ではupper_bound）を検索します。lower_boundからupperboundの直前までの要素は、探しているものです（java.util.SortedSet、subset（key、key）に関して）。
したがって、標準の二分探索に2つの異なるわずかな変更を加える必要があります。それでもプローブし、プローブでの比較を使用して、探している値が存在する必要のある領域を絞り込みます。探している要素（最初の等しい値）は、これまでの範囲の最初の要素とプローブしたばかりの値の間のどこかにあることを知っています-すぐに戻ることはできません。
于 2012-08-27T15:32:06.283 に答える
3
bsearchとの一致を見つけたら、一致しなくなるまで両側を再帰的にbsearchします。
擬似コード：
range search (type *array) {
int index = bsearch(array, 0, array.length-1);
// left
int upperBound = index -1;
int i = upperBound;
do {
upperBound = i;
i = bsearch(array, 0, upperBound);
} while (i != -1)
// right
int lowerBound = index + 1;
int i = lowerBound;
do {
lowerBound = i;
i = bsearch(array, lowerBound, array.length);
} while (i != -1)
return range(lowerBound, UpperBound);
}
ただし、コーナーケースはカバーされていません。これにより、複雑さが（O（logN））に保たれると思います。
于 2012-08-27T16:03:25.003 に答える
2
これは、使用するバイナリ検索の実装によって異なります。
- Javaおよび.NETでは、バイナリ検索により任意の要素が得られます。探している範囲を取得するには、両方の方法を検索する必要があります。
- C ++では、
equal_rangeメソッドを使用して、1回の呼び出しで必要な結果を生成できます。
等しい範囲が長すぎて線形に反復できない場合のJavaおよび.NETでの検索を高速化するには、先行要素と後続要素を検索し、検出した範囲の中央の値を取得します。両端。
2番目の二分探索のためにこれが遅すぎる場合は、両端を同時に検索する独自の検索を作成することを検討してください。これは少し面倒かもしれませんが、より速く実行されるはずです。
于 2012-08-27T15:26:26.907 に答える
2
まず、（「通常の」バイナリ検索を使用して）並べ替え可能なプロパティを指定して単一の要素のインデックスを検索し、次にリスト内の要素の左右両方を検索して、検索に一致するすべての要素を追加します。基準、要素が基準を満たしていないか、トラバースする要素がなくなったときに一方の端で停止し、左右の端が前述の停止条件を満たしたときに完全に停止します。
于 2012-08-27T15:26:38.447 に答える
2
Javaのこのコードは、 1回のパスでO（logN）時間のソートされた配列内のターゲット値の発生をカウントしています。見つかったインデックスのリストを返すように変更するのは簡単です。ArrayListを渡すだけです。
アイデアは、ターゲット値を持つ連続ブロックの下限と上限になるまで、再帰的にリファインしeて境界を設定することです。b
static int countMatching(int[] arr, int b, int e, int target){
int m = (b+e)/2;
if(e-b<2){
int count = 0;
if(arr[b] == target){
count++;
}
if(arr[e] == target && b!=e){
count++;
}
return count;
}
else if(arr[m] > target){
return countMatching(arr,b,m-1, target);
}
else if(arr[m] < target){
return countMatching(arr, m+1, e, target);
}
else {
return countMatching(arr, b, m-1, target) + 1
+ countMatching(arr, m+1, e, target);
}
}
于 2020-12-15T20:20:11.550 に答える
1
バイナリ検索は要素を返しますか、それとも要素が存在するインデックスを返しますか？インデックスを取得できますか？
リストはソートされているため、一致するすべての要素が隣接して表示されます。標準の検索で返されたアイテムのインデックスを取得できる場合は、一致しないものが見つかるまで、そのインデックスから両方向に検索する必要があります。
于 2012-08-27T15:24:37.813 に答える
0
これを試して。それは驚くほど機能します。
実例、ここをクリック
var arr = [1, 1, 2, 3, "a", "a", "a", "b", "c"]; // It should be sorted array.
// if it arr contain more than one keys than it will return an array indexes.
binarySearch(arr, "a", false);
function binarySearch(array, key, caseInsensitive) {
var keyArr = [];
var len = array.length;
var ub = (len - 1);
var p = 0;
var mid = 0;
var lb = p;
key = caseInsensitive && key && typeof key == "string" ? key.toLowerCase() : key;
function isCaseInsensitive(caseInsensitive, element) {
return caseInsensitive && element && typeof element == "string" ? element.toLowerCase() : element;
}
while (lb <= ub) {
mid = parseInt(lb + (ub - lb) / 2, 10);
if (key === isCaseInsensitive(caseInsensitive, array[mid])) {
keyArr.push(mid);
if (keyArr.length > len) {
return keyArr;
} else if (key == isCaseInsensitive(caseInsensitive, array[mid + 1])) {
for (var i = 1; i < len; i++) {
if (key != isCaseInsensitive(caseInsensitive, array[mid + i])) {
break;
} else {
keyArr.push(mid + i);
}
}
}
if (keyArr.length > len) {
return keyArr;
} else if (key == isCaseInsensitive(caseInsensitive, array[mid - 1])) {
for (var i = 1; i < len; i++) {
if (key != isCaseInsensitive(caseInsensitive, array[mid - i])) {
break;
} else {
keyArr.push(mid - i);
}
}
}
return keyArr;
} else if (key > isCaseInsensitive(caseInsensitive, array[mid])) {
lb = mid + 1;
} else {
ub = mid - 1;
}
}
return -1;
}
于 2017-03-27T22:47:36.033 に答える
0
このための非常に効率的なアルゴリズムが最近発見されました。
アルゴリズムには、両方の変数（入力のサイズと検索されたキーの量）を考慮した対数時間計算量があります。ただし、検索されたキーも並べ替える必要があります。
#define MIDDLE(left, right) ((left) + (((right) - (left)) >> 1))
int bs (const int *arr, int left, int right, int key, bool *found)
{
int middle = MIDDLE(left, right);
while (left <= right)
{
if (key < arr[middle])
right = middle - 1;
else if (key == arr[middle]) {
*found = true;
return middle;
}
else
left = middle + 1;
middle = MIDDLE(left, right);
}
*found = false;
/* left points to the position of first bigger element */
return left;
}
static void _mkbs (const int *arr, int arr_l, int arr_r,
const int *keys, int keys_l, int keys_r, int *results)
{
/* end condition */
if (keys_r - keys_l < 0)
return;
int keys_middle = MIDDLE(keys_l, keys_r);
/* throw away half of keys, if the key on keys_middle is out */
if (keys[keys_middle] < arr[arr_l]) {
_mkbs(arr, arr_l, arr_r, keys, keys_middle + 1, keys_r, results);
return;
}
if (keys[keys_middle] > arr[arr_r]) {
_mkbs(arr, arr_l, arr_r, keys, keys_l, keys_middle - 1, results);
return;
}
bool found;
int pos = bs(arr, arr_l, arr_r, keys[keys_middle], &found);
if (found)
results[keys_middle] = pos;
_mkbs(arr, arr_l, pos - 1, keys, keys_l, keys_middle - 1, results);
_mkbs(arr, (found) ? pos + 1 : pos, arr_r, keys, keys_middle + 1, keys_r, results);
}
void mkbs (const int *arr, int N, const int *keys, int M, int *results)
{ _mkbs(arr, 0, N - 1, keys, 0, M - 1, results); }
これがCでの実装と公開を目的としたドラフトペーパーです： https ：//github.com/juliusmilan/multi_value_binary_search
ユースケースを共有していただけますか？
于 2018-11-24T09:40:59.950 に答える
0
あなたはあなたの問題のために以下のコードを使うことができます。ここでの主な目的は、最初にキーの下限を見つけ、次にキーの上限を見つけることです。後で、インデックスの違いを取得し、答えを取得します。2つの異なる関数を使用するのではなく、同じ関数の上限と下限を見つけるために使用できるフラグを使用できます。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int bin_search(int a[], int low, int high, int key, bool flag){
long long int mid,result=-1;
while(low<=high){
mid = (low+high)/2;
if(a[mid]<key)
low = mid + 1;
else if(a[mid]>key)
high = mid - 1;
else{
result = mid;
if(flag)
high=mid-1;//Go on searching towards left (lower indices)
else
low=mid+1;//Go on searching towards right (higher indices)
}
}
return result;
}
int main() {
int n,k,ctr,lowind,highind;
cin>>n>>k;
//k being the required number to find for
int a[n];
for(i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
lowind = bin_search(a,0,n-1,k,true);
if(lowind==-1)
ctr=0;
else{
highind = bin_search(a,0,n-1,k,false);
ctr= highind - lowind +1;
}
cout<<ctr<<endl;
return 0;
}
于 2019-01-30T05:44:23.327 に答える
0
2つの検索を実行できます。1つは範囲の前のインデックス、もう1つは後のインデックスです。前と後が繰り返される可能性があるため、floatを「一意の」キーとして使用します。
static int[] findFromTo(int[] arr, int key) {
float beforeKey = (float) ((float) key - 0.2);
float afterKey = (float) ((float) key + 0.2);
int left = 0;
int right = arr.length - 1;
for (; left <= right;) {
int mid = left + (right - left) / 2;
float cur = (float) arr[mid];
if (beforeKey < cur)
right = mid - 1;
else
left = mid + 1;
}
leftAfter = 0;
right = arr.length - 1;
for (; leftAfter <= right;) {
int mid = left + (right - leftAfter) / 2;
float cur = (float) arr[mid];
if (afterKey < cur)
right = mid - 1;
else
left = mid + 1;
}
return new int[] { left, leftAfter };
}
于 2020-06-23T15:28:57.190 に答える