12

私は配列を持っています

Values array: 12 20 32 40 52
              ^  ^  ^  ^  ^
              0  1  2  3  4

数値が含まれる範囲のインデックスを見つけるためにバイナリ検索を実行する必要があります。例えば：

  1. 数値 -> 19 (インデックス 0 と 1 の間にある) を指定すると、0 を返します
  2. 数値 -> 22 (インデックス 1 と 2 の間にある) を指定すると、1 を返します
  3. 数値 -> 40 (インデックス 3 と 4 の間にある) を指定すると、3 を返します。

二分探索を次のように実装したところ、これはケース 1 と 3 では正しくなりますが、ケース 2 または 52、55 32 などを検索すると正しくなくなります。

#include <iostream>
using namespace std;

int findIndex(int values[], int number, unsigned first, unsigned last)
{
    unsigned midPoint;
    while(first<last)
    {
        unsigned midPoint = (first+last)/2;
        if (number <= values[midPoint])
            last = midPoint -1;
        else if (number > values[midPoint])
            first = midPoint + 1;
    }
    return midPoint;
}


int main()
{
    int a[] = {12, 20, 32, 40, 52};
    unsigned i = findIndex(a, 55, 0, 4);
    cout << i;
}

などの追加変数の使用は許可されbool foundていません。

4

10 に答える 10

14

C または C++ の範囲は通常、下限を直接指すものとして指定されますが、上限を 1 つ超えています。あなたが極度の自虐的であると感じていない限り、検索においてもその慣習に固執したいと思うでしょう.

あなたがそれに従うと仮定すると、あなたlast = midpoint-1;は間違っています。むしろ、実際に使用する範囲の最後を 1 つ過ぎた値に last を設定する必要があるため、次のようにする必要があります。last = midpoint;

また、実際に必要な比較は 2 つではなく1 つだけです。二分探索では、2 つの境界が等しくない限り、下限または上限のいずれかを中心点に設定するため、どちらを決定するために 1 回の比較を行うだけで済みます。

少なくとも慣例により、C++ では、 、 など<の代わりにすべての比較を行います。上記のいずれも機能しますが、使用の慣例に従うだけで、含まれる型に余分な (不要な) 要件が課せられなくなります。<=><

ほとんどのインタビュアーはおそらく気にしませんが、気にするとオーバーフローする可能性もありますmidpoint = (left + right)/2;。私は一般的に好むだろうmidpoint = left + (right - left)/2;

これらを考慮すると、コードは次のようになります。

template <class T>
T *lower_bound(T *left, T *right, T val) {
    while (left < right) {
        T *middle = left + (right - left) / 2;
        if (*middle < val)
            left = middle + 1;
        else
            right = middle;
    }
    return left;
}

template <class T>
T *upper_bound(T *left, T *right, T val) {
    while (left < right) {
        T *middle = left + (right - left) / 2;
        if (val < *middle)
            right = middle;
        else
            left = middle + 1;
    }
    return left;
}
于 2012-06-07T16:27:26.383 に答える
1

入力用

4

1 3 8 10

4

出力

3 (3 と 8 の最小値)

#include <stdio.h>

int main()
{
   int c, first, last, middle, n, search, array[100];


   scanf("%d",&n);



for (c = 0; c < n; c++)
  scanf("%d",&array[c]);


   scanf("%d", &search);

   first = 0;
   last = n - 1;
   middle = (first+last)/2;

while (first <= last) {

  if (array[middle] < search)
  { 
     first = middle + 1;    }
  else if (array[middle] == search) {

     break;
  }
  else
  {  
     last = middle - 1;
  }

  middle = (first + last)/2;
 }
  printf("%d\n",array[middle]);
   return 0;   
 }
于 2015-10-21T16:34:06.747 に答える
1

これは、 min(A[i]) <= key <=max(A[i])という条件で機能します。 

int binary_search(int A[],int key,int left, int right)
{

  while (left <= right) {
        int middle = left + (right - left) / 2;
        if (A[middle] < key)
            left = middle+1;
        else if(A[middle] > key)
            right = middle-1;
        else
            return middle;
    }
    return (left - 1);
}
于 2012-06-10T12:29:59.623 に答える
0 
binsrch(array, num, low, high) {
if (num > array[high])
     return high;


while(1) {
     if (low == high-1)
          return low;
     if(low >= high)
          return low-1;        
     mid = (low+high)/2
     if (num < arr[mid])
          high = mid;
     else
          low = mid+1;
    }
}
于 2012-06-08T20:30:08.390 に答える
0

成功した通常のバイナリ検索では、キーのインデックスが返されます。キーが見つからない場合は、常に、検索しているキーよりも大きい最小のキーのインデックスで停止します。次の修正されたバイナリ検索アルゴリズムが機能すると思います。

Given sorted array A
Find a key using binary search and get an index. 
If A[index] == key
    return index;
else 
   while(index > 1 && A[index] == A[index -1]) index = index -1;
   return index;
于 2012-06-07T23:22:23.093 に答える
0 
/* binary_range.c (c) 2016 adolfo@di-mare.com  */
/* http://stackoverflow.com/questions/10935635 */

/* This code is written to be easily translated to Fortran */

#include <stdio.h>   /* printf() */
#include <assert.h>  /* assert() */

/** Find the biggest index 'i' such that '*nSEED <= nVEC[i]'.
    - nVEC[0..N-1] is an strict ascending order array.
    - Returns and index in [0..N].
    - Returns 'N' when '*nSEED>nVEC[N-1]'.
    - Uses binary search to find the range for '*nSEED'.
*/
int binary_range( int *nSEED, int nVEC[] , int N ) {
    int lo,hi, mid,plus;

    if ( *nSEED > nVEC[N-1] ) {
        return N;
    }
    for (;;) { /* lo = binary_range_search() */
        lo = 0;
        hi = N-1;
        for (;;) {
            plus = (hi-lo)>>1; /* mid = (hi+lo)/2; */
            if ( plus == 0 ) {   assert( hi-lo==1 );
                if (*nSEED <= nVEC[lo]) {
                    hi = lo;
                }
                else {
                    lo = hi;
                }
            }
            mid = lo + plus; /* mid = lo + (hi-lo)/2; */

            if (*nSEED <= nVEC[mid]) {
                hi = mid;
            }
            else {
                lo = mid;
            }
            if (lo>=hi) { break; }
        }
        break;
    } /* 'lo' is the index */
    /* This implementation does not use division. */
    /* =========================================  */

    assert( *nSEED <= nVEC[lo] );
    return lo;
}

/** Find the biggest index 'i' such that '*nSEED <= nVEC[i]'.
    - nVEC[0..N-1] is an strict ascending order array.
    - Returns and index in [0..N].
    - Returns 'N' when '*nSEED>nVEC[N-1]'.
    - Uses sequential search to find the range for '*nSEED'.
*/
int sequential_range( int* nSEED, int nVEC[] , int N ) {
    int i;
    if ( *nSEED > nVEC[N-1] ) {
        return N;
    }
    i=0;
    while ( i<N ) {
        if ( *nSEED <= nVEC[i] ) { break; }
        ++i;
    }
    return i;
}

/** test->stackoverflow.10935635(). */
void test_10935635() {
{{  /* test.stackoverflow.10935635()                                  */
    /* http://stackoverflow.com/questions/10935635                    */
    /* binary_range search to find the range in which the number lies */
    /*              0  1  2  3  4                                     */
    int nVEC[] = { 12,20,32,40,52 }; int val;
    int N = sizeof(nVEC)/sizeof(nVEC[0]); /* N = DIM(nVEC[]) */

    val=19; val   = binary_range( &val,nVEC,N );

    /* 19 -> [12 < (19) <= 20] -> return 1 */
    val=19; assert( binary_range( &val,nVEC,N ) == 1 );

    /* 22 -> [20 < (22) <= 32] -> return 2 */
    val=22; assert( binary_range( &val,nVEC,N ) == 2 );

    /* 40 -> [32 < (40) <= 40] -> return 3 */
    val=40; assert( binary_range( &val,nVEC,N ) == 3 );

    /* Everything over 52 returns N */
    val=53; assert( binary_range( &val,nVEC,N ) == N );
}}
}

/** Test program. */
int main() {
    if (1) {
        printf( "\ntest_10935635()" );
        test_10935635();
    }
    printf( "\nEND" );
    return 0;
}

/* Compiler: gcc.exe (tdm-1) 4.9.2 */
/* IDE:      Code::Blocks 16.01    */
/* Language: C && C++              */

/* EOF: binary_range.c */
于 2016-07-16T21:11:06.313 に答える
0

これがより具体的な答えです

int findIndex(int values[],int key,int first, int last)
{
    if(values[first]<=key && values[first+1]>=key)// stopping condition
    {
        return first;
    }

   int imid=first+(last-first)/2;

   if(first==last || imid==first)
   {
        return -1;
   }
   if(values[imid]>key)
   {
        return findIndex(values,key,first,imid);
    }
    else if(values[imid]<=key)
    {
        return findIndex(values,key,imid,last);
    }

}

これはあなたが探していたものとより一致していると思います...そして、このことの最後の値については説明しません

于 2013-05-17T20:31:18.793 に答える