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


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

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

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

4 встретился с индексом 2.
Есть 2 экземпляра по 4 в массиве.

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

-4 не в массиве.

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

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

Экс: 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;
}   


26034
139
задан 14 марта 2010 в 01:03 Источник Поделиться
Комментарии
15 ответов

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

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

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

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

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

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

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

В духе "шоу, не говори", вот как я бы написал задание (непроверенных, не откомпилированный) (отредактированы, чтобы соответствовать требуемой функции подписи):

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

103
ответ дан 14 марта 2010 в 02:03 Источник Поделиться

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

if (condition)
consequence;
statementx;
...

стиль фугасе просто жду другой (или даже той же) разработчику расширить его:

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

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

61
ответ дан 14 марта 2010 в 12:03 Источник Поделиться

В дополнение ко многим другим замечания следующие:

m = (hi + lo)/2;

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

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

Во-вторых, линия:

m=m;

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

50
ответ дан 14 марта 2010 в 06:03 Источник Поделиться

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


  • Бинарный поиск должен быть отделен от "найди самый длинный путь из одинаковых элементов, содержащих этот показатель".

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

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

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

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


24
ответ дан 14 марта 2010 в 02:03 Источник Поделиться

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

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

24
ответ дан 15 марта 2010 в 01:03 Источник Поделиться

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

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

18
ответ дан 14 марта 2010 в 01:03 Источник Поделиться

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

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

17
ответ дан 14 марта 2010 в 01:03 Источник Поделиться

Это только мне кажется, или я единственный, кто будет осуществлять это в абсолютно разных мода?

Глядя на требования задачи:


  1. Определить, если элемент присутствует

  2. Если представить возвращение индекса в массиве первого вхождения

  3. Если представить возвращать количество вхождений

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

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

unordered_map (с++)

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

Редактировать

Что касается стоимости создания хэш:

Установка постоянной затраты, понесенные только один раз. Хотя я не скажу, что это не имеет значения, есть ограниченное число случаев, когда это делает; обычно, когда у вас либо очень небольших наборов данных или выполните алгоритм очень небольшое количество раз. Кроме того, что стоимость установки амортизируется во всех выполнений алгоритма. Алгоритм, который требует N установки но выполнения, в Биго(1) до сих пор бьет алгоритм, который требует 0 установки, но выполняет в Биго(журнал N) время, если вы выполняете это очень небольшое количество раз.

13
ответ дан 14 марта 2010 в 07:03 Источник Поделиться

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

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

9
ответ дан 14 марта 2010 в 01:03 Источник Поделиться

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

Таким образом, мы можем запустить бинарный поиск по большей мере 2 раза - нет необходимости, чтобы запустить его второй раз, если первые сообщения значение не найдено - и вернуть количество матчей (последний индекс - первый индекс + 1). Я прохожу в пос переменную как указатель, так что мы можем эффективно "вернуть" 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;
}

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

9
ответ дан 14 марта 2010 в 11:03 Источник Поделиться

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

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

Однако, стиль программирования-это то, что вы должны постоянно работать, а не только при подготовке к интервью. Вы не собираетесь менять многое за это время. Я бы взял больше радиус обзора и попытаться получить некоторые C++, C# и Java и опыт под вашим поясом, может быть, PHP или Perl, или Ruby или Python, работа continouously по программированию лучше, может почитать книги или статьи о собеседовании и составлении резюме, и продолжать применять.

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

9
ответ дан 14 марта 2010 в 07:03 Источник Поделиться

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

7
ответ дан 14 марта 2010 в 01:03 Источник Поделиться

Я бы коэффициент бинарного поиска как отдельная процедура.

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

Я предпочитаю конвенции верблюжьего, и более осмысленные имена переменных.

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

7
ответ дан 14 марта 2010 в 01:03 Источник Поделиться

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

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

Слишком много комментариев. Я могу слышать вас сейчас: "он что, сдурел??". Серьезно. Код должен говорить как можно больше для себя. Каждый раз, когда вы начинаете писать комментарий, думаю: "есть ли способ я могу сделать код достаточно ясно, чтобы избежать этот комментарий?". Это забастовка три.

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

7
ответ дан 14 марта 2010 в 07:03 Источник Поделиться

Это то, что я бы сдал, простой, чистый и легкий для чтения:

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

Так что ИМХО все это бинарные вякать поиска попадает под категорию "преждевременная оптимизация" на этот простой вопрос. :-)

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

Последнее редактирование: добавление 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;
}
}

7
ответ дан 14 марта 2010 в 08:03 Источник Поделиться