Поиск элемента в отсортированном массиве

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

  

Вам предоставляется отсортированный массив целых чисел, например {1, 2, 4, 4, 5, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 11, 13 }. Теперь вы должны написать программу (на C или C ++, но я выбрал C), которая запрашивает у пользователя поиск элемента. Затем программа будет искать элемент. Если он найден, то он должен вернуть первый индекс, в котором была найдена запись, и количество экземпляров этого элемента. Если элемент не найден, то он должен возвращать «не найден» или что-то подобное. Вот простой запуск (с массивом, который я просто вставил):

Введите номер для поиска: 4

4 было найдено по индексу 2.
В массиве есть 2 экземпляра для 4.

Введите число для поиска: -4.

-4 не находится в массиве.

Они сделали комментарий, что мой код должен хорошо масштабироваться с большими массивами (поэтому я написал бинарный поиск). В любом случае, мой код в основном работает следующим образом:

  • Подсказывает пользователя для ввода.
  • Затем он проверяет, находится ли он в пределах (больше, чем [0] в массиве и меньше, чем самый большой элемент массива).
  • Если это так, я выполняю двоичный поиск.
  • Если элемент найден, я написал два цикла while. Один цикл while будет считаться слева от найденного элемента, а второй цикл while будет считаться справа от найденного элемента. Петли заканчиваются, когда соседние элементы не соответствуют требуемому значению.

EX: 4, 4 , 4, 4, 4

жирный 4 - это значение, в которое приземлился бинарный поиск. Один цикл будет проверяться слева от него, а другой цикл будет проверяться справа от него. Их суммой будет общее количество экземпляров номера четыре.

В любом случае, я не знаю, есть ли какие-либо усовершенствованные методы, которых я пропускаю, или если у меня просто нет фона CS и сделал большую ошибку. Любые конструктивные критические замечания будут оценены!

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>

/* function prototype */

int get_num_of_ints(
            const int* arr,
            size_t r,
            int N,
            size_t* first,
            size_t* count
    );

int main()
{   
    int N;                                 /* input variable */
    int arr[]={1,1,2,3,3,4,4,4,4,5,5,7,7,7,7,8,8,8,9,11,12,12}; /* sorted */
    size_t r = sizeof(arr)/sizeof(arr[0]); /* right bound */
    size_t first;                          /* first match index */
    size_t count;                          /* total number of matches */

    /* prompts the user to enter input */

    printf( "\nPlease input the integer you would like to find.\n" );
    scanf( "%d", &N );

    int a = get_num_of_ints( arr, r, N, &first, &count );

    /* If the function returns -1 then the value is not found.
        Else it is returned */ 

    if( a == -1)    
        printf( "%d has not been found.\n", N );

    else if(a >= 0){
        printf( "The first matching index is %d.\n", first );
        printf( "The total number of instances is %d.\n", count );
    }

    return 0;
}

/* function definition */

int get_num_of_ints(
        const int* arr,
        size_t r,
        int N,
        size_t* first,
        size_t* count)
{
    int lo=0;    /* lower bound for search */
    int m=0;     /* middle value obtained */
    int hi=r-1;  /* upper bound for search */

    int w=r-1;   /* used as a fixed upper bound to calculate the number of
                    right instances of a particular value. */


    /* binary search to find if a value exists */

    /* first check if the element is out of bounds */

    if( N < arr[0] || arr[hi] < N ){
        m = -1;
    }
    else{ /* binary search to find value if it exists within given params */

        while(lo <= hi){
            m = (hi + lo)/2;

            if(arr[m] < N)
                lo = m+1;
            else if(arr[m] > N)
                hi = m-1;
            else if(arr[m]==N){
                m=m;
                break;
            }
        }
        if (lo > hi)    /* if it doesn't we assign it -1 */
         m = -1;
    }   


    /* If the value is found, then we compute left and right instances of it */ 

    if( m >= 0 ){   

        int j = m-1;    /* starting with the first term to the left */
        int L = 0;  /* total number of left instances */

        /* while loop computes total number of left instances */

        while( j >= 0 && arr[j] == arr[m] ){
            L++;
            j--;
        }


        /* There are six possible outcomes of this. Depending on the outcome,
           we must assign the first index variable accordingly */

        if( j > 0 && L > 0 )
            *first=j+1;
        else if( j==0 && L==0)
            *first=m;
        else if( j > 0 && L==0 )
            *first=m;
        else if(j < 0 && L==0 )
            *first=m; 
        else if( j < 0 && L > 0 )
            *first=0;
        else if( j=0 && L > 0 )
            *first=j+1;

        int h = m + 1;  /* starting with the first term to the right */
        int R = 0;      /* total number of right instances */

        /* while loop computes total number of right instances */
        /* we fixed w earlier so that it's value does not change */ 

        while( arr[h]==arr[m] && h <= w ){
            R++;
            h++;
        }

        *count = (R + L + 1); /* total num of instances stored into count */
        return *first;        /* first instance index stored here */
    }

    /* if value does not exist, then we return a negative value */

    else if( m==-1)
        return -1;
}   
137 голосов | спросил Micky 14 MaramSun, 14 Mar 2010 04:17:52 +03002010-03-14T04:17:52+03:0004 2010, 04:17:52

17 ответов


104

У меня было бы несколько проблем с тем, чтобы нанять кого-то, кто отправил это для образца кода. Вот что я вижу.

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

Во-вторых, (и это то, что действительно убило бы его для меня) имена переменных. Большинство из них - одна или две буквы, и из-за этого код очень нечитабелен. Предоставление описательных имен переменных важно для удобства обслуживания.

В-третьих, игнорирование стандартных библиотек. Если вам не рекомендуется использовать их, вам следует предпочесть стандартные библиотеки, которые имеют реализации бинарного поиска (например, stl или bsearch )

В-четвертых, почему get_num_of_ints возвращает -1, мне кажется волшебное значение; лучше просто установить count = 0 и проверить это.

В-пятых, get_num_of_ints слишком длинный и пытается сделать слишком много. Это должно быть разбито.

Шестой (и это личный выбор), я думаю, что C ++, с STL, намного лучший выбор в этом случае.

В духе «show, not tell», вот как я написал бы задание (непроверенное, нескомпилированное) ( отредактировано в соответствии с требуемой сигнатурой функции ):

#include <iostream>
#include <algorithm>

using namespace std;

// This function signature is required:
int get_num_of_ints(const int* searchBegin, size_t searchSize, int input,
    size_t* first, size_t* count) {
  const int* searchEnd = searchBegin + searchSize;
  const int* result = lower_bound(searchBegin, searchEnd, input);

  if (searchEnd == result || *result != input)
    return -1;

  *first = result - searchBegin;
  *count = upper_bound(result, searchEnd, input) - result;
  return 0;
}

void print_search_results(const int* searchBegin, size_t searchSize, int input) {
  size_t first;
  size_t count; 

  if (get_num_of_ints(searchBegin, searchSize, input, &first, &count) < 0) {
    cout << input << " is not in the array." << endl;
    return;
  }

  cout << input << " was found at index " << first << ". "
       << "There are " << count << " instances for " << input << " in the array."
       << endl;
}

bool read_input(int* input) {
  cout << "Enter a number to search for: ";
  bool succeeded = cin >> *input;
  cout << endl;    
  return succeeded;
}

int main (int argc, char** argv) {
  const int searchNumbers[] = {1, 2, 4, 4, 5, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 11, 13};
  const int searchNumbersSize = sizeof(searchNumbers)/sizeof(searchNumbers[0]);

  while(1) {
     int input;
     if(!read_input(&input)) {
       count << "Bad input, exiting" << endl;
       return 1;
     }

     print_search_results(searchNumbers, searchNumbersSize, input);
  }
}
ответил Todd Gardner 14 MaramSun, 14 Mar 2010 05:40:24 +03002010-03-14T05:40:24+03:0005 2010, 05:40:24
60

По моему опыту,

if (condition)
    consequence;
statementx;
...

стиль - это наземная шахта, которая просто ждет другого (или даже того же) разработчика, чтобы продлить его до:

if (condition)
    consequence1;
    consequence2;
statementx;
...

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

ответил Tomislav Nakic-Alfirevic 14 MarpmSun, 14 Mar 2010 15:00:20 +03002010-03-14T15:00:20+03:0003 2010, 15:00:20
51

В дополнение ко многим другим комментариям:

m = (hi + lo)/2;

- неправильный способ найти средний индекс. Это может переполняться. Вы должны сделать:

m = lo + (hi - lo) / 2;

Во-вторых, строка:

m=m;

не имеет эффекта и может быть устранен.

ответил Alok 14 MaramSun, 14 Mar 2010 09:25:33 +03002010-03-14T09:25:33+03:0009 2010, 09:25:33
23

Случайные наблюдения:

  • Бинарный поиск должен быть отделен от «найти самый длинный пробег идентичных элементов, содержащих этот индекс».

  • Возможно, они хотят логарифмически время в длительности пробега, а не в линейном.

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

    for (first = m; first > arr && *first == arr[m]; first--)
        ;
    for (last = m; last < arr+r-1 && *last == arr[m]; last++)
        ;
    

    Этот код стоит линейно по длительности прогона; если они хотят логарифмически, это становится сложной маленькой проблемой - но, на мой взгляд, сверху как проблема интервью.

ответил Norman Ramsey 14 MaramSun, 14 Mar 2010 05:25:47 +03002010-03-14T05:25:47+03:0005 2010, 05:25:47
23

Я немного опоздал, но это похоже на то, что я могу ожидать увидеть на C ++.

// Interface defined by the problem statement has been adjusted
size_t get_num_of_ints( const int* arr, size_t r, int N, size_t* first )
{
    std::pair<const int *, const int *> range = std::equal_range(arr, arr+r, N);
    size_t count = range.second - range.first;
    if (count > 0 && first != 0)
        *first = range.first - arr;
    return count;
}

Я думаю, что интерфейс сломан как определенный, поэтому я исправил его:)

ответил msandiford 15 MaramMon, 15 Mar 2010 04:43:53 +03002010-03-15T04:43:53+03:0004 2010, 04:43:53
17

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

Это было бы лучше, если бы было много одинаковых элементов, но, что более важно для вопроса интервью, это упростило бы ваш алгоритм. Например, код «6 результатов» довольно волосатый, и наличие такого количества if-else часто считается запахом кода.

ответил 14 MaramSun, 14 Mar 2010 04:29:29 +03002010-03-14T04:29:29+03:0004 2010, 04:29:29
16

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

#include <stdio.h>

int binary_search( const int value, const int *arr, size_t start, size_t end ){
    if( value < arr[start] || value > arr[end] ){
        return -1;
    }

    while(start <= end){
        int pivot = (start+end) >> 1; 
        if(arr[pivot] == value){
            return pivot;
        }else if(arr[pivot] < value){
            start = pivot+1;
        } else if(arr[pivot] > value){
            end = pivot-1;
        } 
    }
    return -1;
}

int get_occurences( int begin, const int *arr, size_t max){
    int counter = 1;
    int cursor = begin;
    while ( (cursor+1) < max && arr[cursor] == arr[cursor+1]) {
        counter++;
        cursor++;
    }
    cursor = begin;
    while ( (cursor-1) > 0 && arr[cursor] == arr[cursor-1]) {
        counter++;
        cursor--;
    }
    return counter;
}


#define MAX 22
int main()
{   
    int value;
    int arr_sorted []={1,1,2,3,3,
                       4,4,4,4,5,
                       5,7,7,7,7,
                       8,8,8,9,11,
                       12,12};    
    size_t arr_size = MAX; // works also the other way               

    printf( "\nPlease input the integer you would like to find.\n" );
    scanf( "%d", &value );
    printf("Searching %d\n", value);
    int pos = binary_search( value, arr_sorted, 0, arr_size-1);

    if( pos == -1) {    
        printf( "%d has not been found.\n", value );
    } else{
        int howmany = get_occurences( pos, arr_sorted, arr_size);
        printf( "The first matching index is %d.\n", pos );
        printf( "The total number of instances is %d.\n", howmany );
    }

    return 0;
}
ответил fabrizioM 14 MaramSun, 14 Mar 2010 04:28:29 +03002010-03-14T04:28:29+03:0004 2010, 04:28:29
12

Это только я, или я единственный, кто мог бы реализовать это совершенно по-другому?

Глядя на требования проблемы:

  1. Определить, присутствует ли элемент
  2. Если присутствует индекс возвращаемого массива первого вхождения
  3. Если присутствует возвращаемое число вхождений

Вы должны думать нестандартно о такой проблеме. В частности, я бы воспользовался решением этого, сбросив массив в хэш в начале программы. Хеш-ключ - это число, а значение - это структура, содержащая индекс первого события и общее количество событий. Вы настраиваете этот хэш как часть запуска /инициализации программы, а затем любые последующие запросы пользователя всегда являются постоянными операциями времени - BigO (1).

У вас не возникнет проблем с реализацией этого в C ++ с STL.

unordered_map (C ++)

Двоичный поиск - это просто неправильное решение этой проблемы.

Edit

Относительно стоимости настройки хеша:

Настройка - это постоянная стоимость, понесенная только один раз. Хотя я не буду говорить, что это не имеет значения, существует ограниченное число случаев, когда это происходит; обычно, когда у вас есть либо очень маленькие наборы данных, либо вы выполняете алгоритм очень мало раз. Помимо этой стоимости установки амортизируются все исполнения алгоритма. Алгоритм, который требует n установки, но выполняет в BigO (1), по-прежнему превосходит алгоритм, который требует установки 0, но выполняет в BigO (log n) время, если вы выполняете его очень малое количество раз.

ответил 14 MaramSun, 14 Mar 2010 10:22:51 +03002010-03-14T10:22:51+03:0010 2010, 10:22:51
9

Я придумал решение, которое является O (log n). Он включает в себя модифицированный двоичный поиск, которому может быть сказано всегда выполнять точно log n сравнения (без раннего взлома, если совпадение найдено), и в зависимости от параметра он будет либо пытаться найти значение влево или вправо в массиве до исчерпания.

Таким образом, мы можем запустить двоичный поиск не более 2 раз - нет необходимости запускать его во второй раз, если первые сообщения не будут найдены, и вернет количество совпадений (последний индекс - первый индекс + 1). Я передаю переменную pos в качестве указателя, чтобы мы могли эффективно «вернуть» 2 значения - количество совпадений и индекс первого совпадения в прогоне.

// returns the number of matches, and sets pos to the index of
// the first match, or -1 if none found
int findMatches(int array[], int size, int searchNum, int* pos)
{
   *pos = binarySearch(array, size, searchNum, -1);
   // if it was found, pos points to a positive number
   if(*pos >= 0)
   {
      int lastIdx = binarySearch(array, size, searchNum, 1);
      return lastIdx - *pos + 1;
   }
   return 0;
}

Затем у меня есть метод двоичного поиска, который принимает дополнительный аргумент, direction, который указывает, хотите ли вы первый индекс двоичного поиска (0), самый ранний (-1) или последний (1).

int binarySearch(int array[], int size, int searchNum, int direction)
{
   int left = 0;
   int right = size - 1;
   int center;
   int pos = -1;

   while(left <= right)
   {
      center = (right + left) >> 1;

      if(array[center] == searchNum)
      {
         pos = center;
         // break early if we want to find the exact match
         if(direction == 0) break;
      }

      // adding 1 to searchNum means we will find the last in the run
      if(array[center] < searchNum + ((direction > 0) ? 1 : 0))
      {
         left = center + 1;
      }
      else
      {
         right = center - 1;
      }
   }

   return pos;
}
ответил Phil 14 MarpmSun, 14 Mar 2010 14:04:20 +03002010-03-14T14:04:20+03:0002 2010, 14:04:20
8

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

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

ответил Mawg 14 MaramSun, 14 Mar 2010 04:27:27 +03002010-03-14T04:27:27+03:0004 2010, 04:27:27
8

Другая возможность заключается в том, что выбор C ++ и C был тестом сам по себе :) Возможно, они были готовы согласиться на кого-то с опытом C, но предпочли бы кого-то с опытом C ++, так что это могло быть фактором.

Если вам действительно интересно, вы можете даже связаться с ними снова и попросить обратную связь.

Тем не менее, стиль программирования - это то, над чем вы должны работать постоянно, а не только при подготовке к собеседованию. В то время вы не будете сильно меняться. Я бы взял более длинный диапазон и попытался получить некоторые C ++, C # и Java-опыт под вашим поясом, возможно, PHP или perl, или ruby ​​или python, постоянно работают над программированием, возможно, читают книгу или статью о собеседовании и возобновлении написания , и продолжать применять.

Я действительно думаю, может быть, им просто не понравилась рубашка, которую вы носили:)

ответил Larry Watanabe 14 MarpmSun, 14 Mar 2010 22:38:15 +03002010-03-14T22:38:15+03:0010 2010, 22:38:15
7

Я бы определил двоичный поиск как отдельную процедуру.

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

Я предпочитаю соглашение camelCase и более значимые имена переменных.

Ваш алгоритм, однако, кажется прекрасным. Вы думали о возможности того, что тест не был большим фактором в принятии решения о найме? Несколько претендентов могли написать одинаково хорошие ответы, и решение было принято по другим критериям.

ответил Larry Watanabe 14 MaramSun, 14 Mar 2010 04:25:01 +03002010-03-14T04:25:01+03:0004 2010, 04:25:01
7

Было ли какое-то конкретное требование, что вы выполняете двоичный поиск в списке? Если бы не было, зачем вы это делаете? Неоправданно избыточное решение - это один удар против вас. * Edit: Увы, вы сказали, что вам нужно сделать это таким образом в вопросе! Ничего, продолжайте *

Почему вы используете имена имен одиночных символов? В таблице символов есть много места для более описательных имен. Это еще одна забастовка.

Слишком много комментариев. Теперь я слышу вас всех: «Он сумасшедший?». Шутки в сторону. Код должен говорить сам по себе как можно больше. Каждый раз, когда вы начинаете писать комментарий, думаете: «Есть ли способ сделать код достаточно ясным, чтобы избежать этого комментария?». Это три удара.

Кодирование - это такое же общение с другими людьми, как и общение с машиной. Ваш стиль кодирования должен отражать это. Code Complete - отличная книга с большим количеством полезных советов по стилю кодирования. Прочитайте первые несколько глав и снова сформулируйте решение, применяя методы, которые он описывает. Сравните ваши два решения, задавая себе вопрос: «Какой из них мне лучше поддерживать?».

ответил 14 MaramSun, 14 Mar 2010 10:21:10 +03002010-03-14T10:21:10+03:0010 2010, 10:21:10
6

Прошло много времени с тех пор, как я использовал C ++, поэтому я не мог писать его сейчас, но я знаю, что в STL были алгоритмы, которые сделали бы очень короткую работу. Реализация вашего собственного бинарного поиска, вероятно, является признаком потенциального работодателя, что вы новичок. Тот факт, что вы можете реализовать это хорошо, но который вы бы выбрали, когда такие алгоритмы уже реализованы для вас, может быть обескураживающим для них.

ответил Carl Manaster 14 MaramSun, 14 Mar 2010 04:23:27 +03002010-03-14T04:23:27+03:0004 2010, 04:23:27
6

Это то, что я бы включил, прост и понятен:

Я изменил его, чтобы проверить время с массивом в 300 миллионов ints, и даже в моей старой системе он обнаружил значения «наихудшего случая» (те, что были в конце массива) примерно через секунду (занял 6 секунд до заполнить массив при запуске).

Таким образом, IMHO все это бинарное поисковое устройство попадает под категорию «предварительная зрелая оптимизация» для этого простого вопроса об интервью. : -)

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

Последнее редактирование: добавление функции FindStartingPoint () для оптимизации скорости.

/*****************************************************************
   Module: FindInts.cpp
   Author: Ron Savage
     Date: 03/13/2010

  Description:
  This program prompts the user for an integer, searches for it
  in a given sorted array of integers and prints the first location 
  and number of matches in the array.

  Modification History:
  Date       Init Comment
  03/14/2010 RS   Added a recursive FindStartingPoint function to
                  find a good starting point for the linear search.
  03/14/2010 RS   Added a 300 million int array to test timing.
  03/13/2010 RS   Created.
*****************************************************************/
#include <stdafx.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>

/* function prototype */
void   FillArray( int* searchList, size_t listSize);
int*   FindStartPoint( int* searchList, size_t listSize, int numberToFind );
size_t FindMatches( int* searchList, size_t listSize, int numberToFind, size_t* firstMatchIndex, size_t* matchCount );

/*****************************************************************
   Function: main()
     Author: Ron Savage
       Date: 03/13/2010

  Description:
  Entry point to the program.
*****************************************************************/
int main()
    {
    int userInput = 0;
    int *valueList = 0;

    // Allocate an array of 300 million ints
    size_t listSize = 300000000;
    if (valueList = (int*) malloc(listSize * sizeof(int)))
        {
        size_t firstMatchIndex = 0;
        size_t matchCount = 0;

        /* Fill the array with some values */
        FillArray(valueList, listSize);

        /* prompt the user to enter input */
        printf( "\nPlease input the integer you would like to find.\n" );
        scanf_s( "%d", &userInput );

        /* Search the list for the value entered */
        size_t iterations = 0;
        iterations = FindMatches( valueList, listSize, userInput, &firstMatchIndex, &matchCount );

        /* Display the results if found */
        if ( matchCount > 0 )
            {
            printf("\n%d matches for [%d] were found, starting at index %d in %ld iterations.\n", matchCount, userInput, firstMatchIndex, iterations);
            }
        else
            {
            printf("\nNo matches for [%d] were found.\n", userInput);
            }
        }
    else
        {
        printf("\nCouldn't allocate memory for [%ld] ints.\n", listSize);
        }
    }

/*****************************************************************
   Function: FindMatches()
     Author: Ron Savage
       Date: 03/13/2010

  Description:
  This function searches the searchList for the value entered
  by the user (numberToFind) and returns the first index and 
  count of the matches.
*****************************************************************/
size_t FindMatches( int* searchList, size_t listSize, int numberToFind, size_t* firstMatchIndex, size_t* matchCount )
    {
    // Set the default values if no matches are found
    *firstMatchIndex    = 0;
    *matchCount         = 0;

    // Find the start point of the number
    int* startPoint   = FindStartPoint( searchList, listSize, numberToFind );

    // Loop through the list looking for matches, exit early if we pass the value in the sorted list.
    size_t searchIndex       = 0;
    size_t searchInterations = 0;
    size_t startIndex        = startPoint - searchList;
    for (searchIndex = startIndex; searchIndex < listSize; searchIndex++)
        {
        searchInterations++;

        if ( searchList[searchIndex] == numberToFind )   if ( ++(*matchCount) == 1 ) *firstMatchIndex = searchIndex;

        if ( searchList[searchIndex] > numberToFind ) break;
        }

    return(searchInterations);
    }

/*****************************************************************
   Function: FindStartPoint()
     Author: Ron Savage
       Date: 03/14/2010

  Description:
  This function checks to see if the numberToFind is in the top
  or bottom half of the searchList, then recursively calls itself
  on each subsequently smaller sub-list until a starting point
  at or slightly before the first numberToFind is found.
*****************************************************************/
int* FindStartPoint( int* searchList, size_t listSize, int numberToFind )
    {
    // Check the value in the middle, to determine which half the number is in
    size_t middleIndex  = listSize / 2;

    // Recurse into this function for just the first half of the list
    if ( searchList[middleIndex] >= numberToFind && middleIndex > 1 ) 
        {
        return(FindStartPoint(searchList, middleIndex, numberToFind ));
        }

    // Recurse into this function for just the last half of the list
    if ( searchList[middleIndex] < numberToFind && middleIndex > 1 ) 
        {
        return(FindStartPoint(&searchList[middleIndex], middleIndex, numberToFind ));
        }

    return(searchList);
    }

/*****************************************************************
   Function: FillArray()
     Author: Ron Savage
       Date: 03/13/2010

  Description:
  This function fills the array with a sorted list of values.
*****************************************************************/
void FillArray( int* searchList, size_t listSize)
    {
    size_t searchIndex  = 0;
    int    value        = 0;

    for (searchIndex = 0; searchIndex < listSize; searchIndex++)
        {
        searchList[searchIndex] = value++/100;
        }
    }
ответил Ron Savage 14 MaramSun, 14 Mar 2010 11:27:59 +03002010-03-14T11:27:59+03:0011 2010, 11:27:59
3

Чуть больше, чем nitpick, но, вероятно, не достаточно большая проблема, чтобы вас выгнать:

Почему вы явно проверяете окончательный случай else в три исчерпывающий if ... else заявления? Как правило, либо они должны иметь другой оператор else, чтобы уловить любой возможный непредвиденный случай, либо во всех этих случаях вы должны прокомментировать окончательное предложение if:

if( a < 0)    
    printf( "%d has not been found.\n", N );
else //if(a >= 0)
{ ...


if(arr[m] < N)
    lo = m+1;
else if(arr[m] > N)
    hi = m-1;
else //if(arr[m]==N)
{ ...

    if( j > 0 && L > 0 )
        *first=j+1;
    else if( j==0 && L==0)
        *first=m;
    else if( j > 0 && L==0 )
        *first=m;
    else if(j < 0 && L==0 )
        *first=m; 
    else if( j < 0 && L > 0 )
        *first=0;
    else //if( j=0 && L > 0 )
        *first=j+1;

Обратите внимание также на опечатку в этом последнем условии.

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

BTW не требует повторного использования вашего отдельного заявления, а затем /else - в качестве подтверждения этого; это было не то, что я собирался обсудить.

ответил Mark Hurd 23 J000000Thursday15 2015, 17:06:40
0

Ваше решение работает, но, как сказано в предыдущих ответах, оно работает в худшем случае линейного времени. Вы можете уменьшить его до наихудшего логарифмического значения, переписав две функции в стандартной библиотеке C ++ на C: а именно std :: lower_bound и std :: upper_bound . std::lower_bound вернет «итератор» (указатель на C, вызовите его const int* res) в первый соответствующий элемент (со значением N). Если таковых нет, у нас будет N != *res. Если указатель верен, выполните std::upper_bound, а количество совпадающих элементов будет просто разницей между результатом std::upper_bound и std::lower_bound. Кроме того, что касается API, я предлагаю вам вставить значение нуля в count всякий раз, когда нет совпадения. Соединяя все части, вы можете получить что-то вроде этого:

#include <stdio.h>

static const int* upper_bound(const int* begin,
                              const int* end,
                              const int value)
{
    size_t count;
    size_t step;
    const int* iter;
    count = end - begin;

    while (count > 0)
    {
        iter = begin + (step = (count >> 1));

        if (*iter <= value)
        {
            begin = iter + 1;
            count -= step + 1;
        }
        else
        {
            count = step;
        }
    }

    return begin;
}

static const int* lower_bound(const int* begin,
                              const int* end,
                              const int value)
{
    size_t count;
    size_t step;
    const int* iter;
    count = end - begin;

    while (count > 0)
    {
        iter = begin + (step = (count >> 1));

        if (*iter < value) /* upper_bound compares "*iter <= value" */
        {
            begin = iter + 1;
            count -= step + 1;
        }
        else
        {
            count = step;
        }
    }

    return begin;
}

void get_number_of_ints(const int* array,
                       size_t array_length,
                       int target_value,
                       size_t* first_index,
                       size_t* count)
{
    const int* iter1;
    const int* iter2;

    iter1 = lower_bound(array, array + array_length, target_value);

    if (*iter1 != target_value)
    {
        /* No match. */
        *count = 0;
        return;
    }

    iter2 = upper_bound(array, array + array_length, target_value);
    *first_index = (size_t)(iter1 - array);
    *count = (size_t)(iter2 - iter1);
}

int main()
{
    int N;                                 /* input variable */
    int arr[]={1,1,2,3,3,4,4,4,4,5,5,7,7,7,7,8,8,8,9,11,12,12}; /* sorted */
    size_t r = sizeof(arr)/sizeof(arr[0]); /* right bound */
    size_t first;                          /* first match index */
    size_t count;                          /* total number of matches */

    /* prompts the user to enter input */

    printf( "\nPlease input the integer you would like to find.\n" );
    scanf( "%d", &N );

    get_number_of_ints(arr, r, N, &first, &count);

    if (count == 0)
    {
        printf("%d not found!\n", N);
    }
    else
    {
        printf("%d found at %zu, length %zu.\n", N, first, count);
    }

    return 0;
}
ответил coderodde 7 Jpm1000000pmSun, 07 Jan 2018 17:26:08 +030018 2018, 17:26:08

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

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132