Вопрос по c++ – Двоичный поиск, чтобы найти диапазон, в котором лежит число

7

У меня есть массив

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

по которому я должен выполнить бинарный поиск, чтобы найти индекс диапазона, в котором лежит число. Например:

Given the number -> 19 (It lies between index 0 and 1), return 0 Given the number -> 22 (It lies between index 1 and 2), return 1 Given the number -> 40 (It lies between index 3 and 4), return 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 не допускается.

Почемуfirst а такжеlast закомментирован? Что такое0, 4 делать в объявлении функции? Shahbaz
Зачем возвращать 0, если он находится между индексами 1 и 2 ?! Shahbaz
@Shahbaz и / или Ray Toal: Ваши правки делают функцию действительно осмысленной, но поскольку вопрос в том, почему код OP не работает, мы понятия не имеем, написано ли вами то, что написано в OP. спрашивать о. Benjamin Lindley
Это даже не компилируется. Попробуй в идеоне (ideone.com) например. slaphappy
@ Shahbaz: отредактировано. Спасибо за указание user1372448

Ваш Ответ

9   ответов
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;
1

Почему бы не использовать стандартные библиотечные функции?

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
    for (int input = 10; input < 55; input++) {
        cout << input << ": ";

        // Your desire:
        vector<int> v = { 12, 20, 32, 40, 52 };
        if (input < v.front() || input > v.back()) {
            cout << "Not found" << endl;
        } else {
            auto it = upper_bound(v.begin(), v.end(), input);
            cout << it - v.begin() - 1 << endl;
        }
    }
}

Примечание: довольно крутой сайт -http://en.cppreference.com/w/cpp/algorithm

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;
    }
}
0

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);
}
1

INPUT

4

1 3 8 10

4

OUTPUT

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;   
 }
12

нижнюю границу, но за верхнюю границу. Если вы не чувствуете себя крайне мазохистски, вы, вероятно, захотите придерживаться этого соглашения и в своем поиске.

Предполагая, что вы будете следовать этому, вашlast = midpoint-1; это неверно. Скорее, вы хотите установить последний на одинpast конец диапазона, который вы на самом деле собираетесь использовать, поэтому он должен бытьlast = midpoint;

Вам также действительно нужноone Сравнение, а не два. В бинарном поиске до тех пор, пока две границы не равны, вы собираетесь установить либо нижнюю, либо верхнюю границу центральной точки, поэтому вам нужно сделать только одно сравнение, чтобы решить, какие из них.

По крайней мере, по соглашению, в 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;
}
Установка 'last = midPoint' в приведенном выше сообщении, похоже, не дают правильного ответа. user1372448
@ user1372448: код, который я добавил выше, прошел все тесты, которые мне удалось создать.
@JerryCoffin: Согласно этому вопросу, 12-20 - это один диапазон, 20-32 - другой, 32-40, 40-52, 52- и так далее. Я попробовал функцию lower_bound как этот pastebin.com/RJc3xRmw. Я ожидал бы, что значения между [12, 20) дадут индекс 0, тогда как это дает индекс 0 только для 12, а не для значений 13-19, потому что это то, что установлено между ними. user1372448
Ваша нижняя граница на самом деле является функцией того, что вы называетеmasochistic путь.Left во-первых,Right последний Спрашиваю, потому что я все еще не получаю правильную информацию и проверяю свой код. user1372448
@ user1372448: нет, lower_bound ожидает начало / конец + 1 в качестве входных данных и поддерживает их все время. Это немного отличается от того, что вы просите, хотя. Если число присутствует, оно возвращает индекс (первое вхождение) этого числа. Если число отсутствует, оно возвращает индекс, по которому вы его вставили, где вы хотите, чтобы индекс был непосредственно перед точкой его вставки.
0
/* binary_range.c (c) 2016 [email protected]  */
/* 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 */
Эта реализация решает аналогичную проблему. Тест для(hi-lo)==1 необходимо избегать бесконечного цикла, когда 2 границы являются последовательными. Сдвиг> 1 используется, чтобы избежать деления на 2.
0

что это старая тема, но так как мне пришлось решать подобную проблему, я решил поделиться ею. Учитывая набор неперекрывающихся диапазонов целых чисел, мне нужно проверить, находится ли данное значение в любом из этих диапазонов. Следующее (в Java) использует модифицированный двоичный поиск, чтобы проверить, находится ли значение в отсортированном (от низшего к самому высокому) наборе целочисленных диапазонов.

/**
 * Very basic Range representation for long values
 *
 */
public class Range {

private long low;
private long high;

public Range(long low, long high) {
    this.low = low;
    this.high = high;
}

public boolean isInRange(long val) {
    return val >= low && val <= high;
}

public long getLow() {
    return low;
}

public void setLow(long low) {
    this.low = low;
}

public long getHigh() {
    return high;
}

public void setHigh(long high) {
    this.high = high;
}

@Override
public String toString() {
    return "Range [low=" + low + ", high=" + high + "]";
}
}



import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//Java implementation of iterative Binary Search over Ranges
class BinaryRangeSearch { 
// Returns index of x if it is present in the list of Range, 
// else return -1 
int binarySearch(List<Range> ranges, int x) 
{ 

    Range[] arr = new Range[ranges.size()];
    arr = ranges.toArray(arr);
    int low = 0, high = arr.length - 1; 
    int iters = 0;
    while (low <= high) { 
        int mid = low + (high - low) / 2; // find mid point

        // Check if x is present a
        if (arr[mid].getLow() == x) {
            System.out.println(iters + " iterations");
            return mid;                 
        }

        // If x greater, ignore left half 
        if (x > arr[mid].getHigh()) {
            low = mid + 1; 
        }
        else if (x >= arr[mid].getLow()) {
            System.out.println(iters + " iterations");
            return mid;
        }

        // If x is smaller, ignore right half of remaining Ranges
        else
            high = mid - 1; 
        iters++;
    } 

    return -1; // not in any of the given Ranges
} 

// Driver method to test above 
public static void main(String args[]) 
{ 
    BinaryRangeSearch ob = new BinaryRangeSearch(); 

    // make a test list of long Range
    int multiplier = 1;

    List<Range> ranges = new ArrayList<>();
    int high = 0;
    for(int i = 0; i <7; i++) {

        int low = i + high;
        high = (i+10) * multiplier;
        Range r = new Range(low, high);
        multiplier *= 10;
        ranges.add(r);
    }

    System.out.println(Arrays.toString(ranges.toArray()));

    int result = ob.binarySearch(ranges, 11); 
    if (result == -1) 
        System.out.println("Element not present"); 
    else
        System.out.println("Element found at "
                        + "index " + result); 
} 
} 
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);
    }

}

Я чувствую, что это в большей степени соответствует тому, что вы искали ... и мы не будем тратить время на последнюю ценность в этой вещи

Похожие вопросы