следующее большее число в отсортированном массиве

Question

У меня есть отсортированный массив (в порядке возрастания), и я хочу найти индекс числа в массиве, который является следующим наибольшим числом к ​​данному число. Например, если у меня есть 67 в качестве данного числа и если у меня есть массив х = (23,36,45,62,79,103,109), тогда как мне получить индекс 5 от х (до получить 79, который является следующим по величине к 67) без использования цикла for?

Answer 1

Это домашняя работа?

Вы можете сделать это довольно легко с помощью рекурсивного вызова, каждый раз разделяя массив пополам.

Answer 2

Вы должны использовать бинарный поиск. Смотрите википедию. http://en.wikipedia.org/wiki/Binary_search

Также в C вы можете использовать встроенную библиотечную функцию bsearch для двоичного поиска. http://www.cplusplus.com/reference/clibrary/cstdlib/bsearch/

Answer 3

Я проверил это:

~> a.out ARR = 23 36 45 62 79 103 109 значение: 79, индекс: 4

в этом коде нет проверки границ...

#include <stdio.h>

int findNum(int, int *, int *); 

int main(int argc, char** argv) {
  int list[7] = {23,36,45,62,79,103,109};
  int i, val, idx = 0;

  printf("ARR=");
  for (i=0; i<7; i++) {
    printf("%d ", list[i]);
  }

  val = findNum(67, list, &idx);
  printf("\nvalue: %d, index: %d\n\n", val, idx);

  return(0);
}

int findNum(int num, int *list, int *idx) {

  if (*list <= num) {
    *idx = (*idx)++;
    return(findNum(num,list+1,idx));
  }

}

Answer 4

a: массив.низкий: начальный индекс.высокий: самый большой индекс.число: число для поиска.

** нижний индекс int (int a [], int low, int high, int number)

{

int mid;

if (number > a[low] && number < a[high])
{

    mid = (low+high)/2;

if a[mid] > number 
        {
             if ( a[mid-1]<=number)
           return mid;
            else return subscript(a, low, mid-1); 
      }

if a[mid]<=number 
         {
             if( a[mid+1] > number)
              return mid+1;
             else
              return subscript(a, mid+1, high);
        }
}

return -1;}

Answer 5

Следующий код найдет индекс следующего наибольшего числа в массиве.Но ...

#include <stdio.h>

int findIndex(int *array, int value) {
    static int index = 0;
    index++;
    if(array[index] > value)
        printf("Index: %d\n", index);
    else
        return findIndex(array, value);
} // findIndex

int main() {
    int x[] = {23, 36, 45, 62, 79, 103, 109};

    findIndex(x, 67);

    return 0;
}

В этом коде есть недостаток.Вы заметили это?