Поиск элемента в отсортированном массиве
Я подавал заявку на должность, и они попросили меня заполнить для них проблему кодирования. Я сделал это и представил его, но позже узнал, что меня отклонили с позиции. В любом случае, у меня есть эклектичный фон программирования, поэтому я не уверен, что мой код сильно ошибочен или у меня просто не было лучшего решения. Я хотел бы опубликовать свой код и получить некоторые отзывы об этом. Прежде чем я это сделаю, вот описание проблемы:
Вам предоставляется отсортированный массив целых чисел, например
{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;
}
17 ответов
У меня было бы несколько проблем с тем, чтобы нанять кого-то, кто отправил это для образца кода. Вот что я вижу.
Во-первых, обращаясь к общему дизайну, алгоритм является субоптимальным и в худшем случае является линейным, а не логарифмическим с наихудшим регистром, поскольку он не использует двоичный поиск для нахождения количества элементов, а линейный.
Во-вторых, (и это то, что действительно убило бы его для меня) имена переменных. Большинство из них - одна или две буквы, и из-за этого код очень нечитабелен. Предоставление описательных имен переменных важно для удобства обслуживания.
В-третьих, игнорирование стандартных библиотек. Если вам не рекомендуется использовать их, вам следует предпочесть стандартные библиотеки, которые имеют реализации бинарного поиска (например, 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;
}
Это только я, или я единственный, кто мог бы реализовать это совершенно по-другому?
Глядя на требования проблемы:
- Определить, присутствует ли элемент
- Если присутствует индекс возвращаемого массива первого вхождения
- Если присутствует возвращаемое число вхождений
Вы должны думать нестандартно о такой проблеме. В частности, я бы воспользовался решением этого, сбросив массив в хэш в начале программы. Хеш-ключ - это число, а значение - это структура, содержащая индекс первого события и общее количество событий. Вы настраиваете этот хэш как часть запуска /инициализации программы, а затем любые последующие запросы пользователя всегда являются постоянными операциями времени - BigO (1).
У вас не возникнет проблем с реализацией этого в C ++ с STL.
Двоичный поиск - это просто неправильное решение этой проблемы.
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;
}