Skip to main content
deleted 1 character in body
Source Link
coderodde
  • 32.3k
  • 15
  • 79
  • 205

Your solution works, yet, as said in previous answers, it runs in worst case linear time. You can reduce it to worstany-case logarithmic by rewriting two functions in the C++ standard library to C: namely, std::lower_bound and std::upper_bound (both will run in \$\Theta(\log N)\$time time on arrays). std::lower_bound will return the "iterator" (pointer in C, call it const int* res) to the first matching element (with value N). If there is no such, we will have N != *res. If the pointer is correct, perform std::upper_bound and the count of matching elements will be simply the difference between the result of std::upper_bound and std::lower_bound. Also, what comes to API, I suggest you insert the value of zero to count whenever there is no match. Putting all pieces together, you may obtain something like this:

Your solution works, yet, as said in previous answers, it runs in worst case linear time. You can reduce it to worst-case logarithmic by rewriting two functions in the C++ standard library to C: namely, std::lower_bound and std::upper_bound (both will run in \$\Theta(\log N)\$time on arrays). std::lower_bound will return the "iterator" (pointer in C, call it const int* res) to the first matching element (with value N). If there is no such, we will have N != *res. If the pointer is correct, perform std::upper_bound and the count of matching elements will be simply the difference between the result of std::upper_bound and std::lower_bound. Also, what comes to API, I suggest you insert the value of zero to count whenever there is no match. Putting all pieces together, you may obtain something like this:

Your solution works, yet, as said in previous answers, it runs in worst case linear time. You can reduce it to any-case logarithmic by rewriting two functions in the C++ standard library to C: namely, std::lower_bound and std::upper_bound (both will run in \$\Theta(\log N)\$ time on arrays). std::lower_bound will return the "iterator" (pointer in C, call it const int* res) to the first matching element (with value N). If there is no such, we will have N != *res. If the pointer is correct, perform std::upper_bound and the count of matching elements will be simply the difference between the result of std::upper_bound and std::lower_bound. Also, what comes to API, I suggest you insert the value of zero to count whenever there is no match. Putting all pieces together, you may obtain something like this:

added 52 characters in body
Source Link
coderodde
  • 32.3k
  • 15
  • 79
  • 205

Your solution works, yet, as said in previous answers, it runs in worst case linear time. You can reduce it to worst-case logarithmic by rewriting two functions in the C++ standard library to C: namely, std::lower_bound and std::upper_bound (both will run in \$\Theta(\log N)\$time on arrays). std::lower_bound will return the "iterator" (pointer in C, call it const int* res) to the first matching element (with value N). If there is no such, we will have N != *res. If the pointer is correct, perform std::upper_bound and the count of matching elements will be simply the difference between the result of std::upper_bound and std::lower_bound. Also, what comes to API, I suggest you insert the value of zero to count whenever there is no match. Putting all pieces together, you may obtain something like this:

Your solution works, yet, as said in previous answers, it runs in worst case linear time. You can reduce it to worst-case logarithmic by rewriting two functions in the C++ standard library to C: namely, std::lower_bound and std::upper_bound. std::lower_bound will return the "iterator" (pointer in C, call it const int* res) to the first matching element (with value N). If there is no such, we will have N != *res. If the pointer is correct, perform std::upper_bound and the count of matching elements will be simply the difference between the result of std::upper_bound and std::lower_bound. Also, what comes to API, I suggest you insert the value of zero to count whenever there is no match. Putting all pieces together, you may obtain something like this:

Your solution works, yet, as said in previous answers, it runs in worst case linear time. You can reduce it to worst-case logarithmic by rewriting two functions in the C++ standard library to C: namely, std::lower_bound and std::upper_bound (both will run in \$\Theta(\log N)\$time on arrays). std::lower_bound will return the "iterator" (pointer in C, call it const int* res) to the first matching element (with value N). If there is no such, we will have N != *res. If the pointer is correct, perform std::upper_bound and the count of matching elements will be simply the difference between the result of std::upper_bound and std::lower_bound. Also, what comes to API, I suggest you insert the value of zero to count whenever there is no match. Putting all pieces together, you may obtain something like this:

Source Link
coderodde
  • 32.3k
  • 15
  • 79
  • 205

Your solution works, yet, as said in previous answers, it runs in worst case linear time. You can reduce it to worst-case logarithmic by rewriting two functions in the C++ standard library to C: namely, std::lower_bound and std::upper_bound. std::lower_bound will return the "iterator" (pointer in C, call it const int* res) to the first matching element (with value N). If there is no such, we will have N != *res. If the pointer is correct, perform std::upper_bound and the count of matching elements will be simply the difference between the result of std::upper_bound and std::lower_bound. Also, what comes to API, I suggest you insert the value of zero to count whenever there is no match. Putting all pieces together, you may obtain something like this:

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