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

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

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

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

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

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

if (condition)
    consequence;
statementx;
...

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

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

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

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

m = (hi + lo)/2;

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

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

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

m=m;

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

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

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

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

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

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

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

Я немного опоздал, но это похоже на то, что я могу ожидать увидеть на 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;
}

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

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

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

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

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

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

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

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

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

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

unordered_map (C ++)

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

Edit

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

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

Я придумал решение, которое является 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;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Я изменил его, чтобы проверить время с массивом в 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;
        }
    }

Чуть больше, чем 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 - в качестве подтверждения этого; это было не то, что я собирался обсудить.

Ваше решение работает, но, как сказано в предыдущих ответах, оно работает в худшем случае линейного времени. Вы можете уменьшить его до наихудшего логарифмического значения, переписав две функции в стандартной библиотеке 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;
}