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

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

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 не допускается.

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

Ответы на вопрос(9)

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

}

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

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

#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

Решение Вопроса

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

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

что это старая тема, но так как мне пришлось решать подобную проблему, я решил поделиться ею. Учитывая набор неперекрывающихся диапазонов целых чисел, мне нужно проверить, находится ли данное значение в любом из этих диапазонов. Следующее (в 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); 
} 
} 

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

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

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

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

Ваш ответ на вопрос