How can I find the largest number in an array that is less than or equal to a random integer?

Question

I am working on an assignment and I'm asked to create an array of fibonacci numbers in a range of 0 to 50,000. Once this array has been initialized I am suppose to create a random number between 2 and 10,000. Then, I'm suppose to compare the members of the fibonacci array with the random number to find the greatest fibonacci number that is less than or equal to the random number.

This is the code that I have so far, it correctly creates the array of fibonacci numbers and the random number. How would I start with comparing the members of the array to the random number?

#include <stdio.h> 
#include <string.h> 
#include <time.h>

void Get_Fibonacci(int n)
{
     int fibArray[25];
     int lower = 2, upper = 10000, count = 1;

     int i, FibRange = 50000;
     int first = 0, second = 1, next = 1;

     printf("%d %d", first, second);

     //Create fibonacci sequence between 0 and 50,000 and store in array
     for (i = 2; (first + second) < FibRange; i++)
     {
         next = first + second;

         fibArray[i] = next;
         printf(" %d\n", fibArray[i]);

         first = second;
         second = next;
     }

     //Create Random Number between 2 and 10,000
     srand(time(0));
     int k;
     for (k = 0; k < count; k++)
     {
         n = (rand() % upper - lower + 1) + lower;
     }

 }

Answer 1

First, need to claify somethings: 1) the for loop for creating a random number is useless since count is always is one 2) n should not be a parameter for the function since you generate a random number in the function 3) the i should start from 0, starting from 2 doesn't make any sense to me. You’re just wasting the first two elements in the array

Largest is the variable that carries the value of the largest element and still smaller than n.

int Largest = fibArray[0];
for(int counter=1; counter<25; counter++){
    if(fibArray[counter]>Largest && fibArray[counter]<n)
        Largest = fibArray[counter];
}
return Largest;

Answer 2

I did a little tweaking to your algorithm. This should do what you are asking. Basically since the Fibonacci sequence combines of sorted numbers, you can do binary search. Also, in your implementation, your array doesn't have to be of size 25 since you are only holding 23 integers. 0 and 1 are saved in independent variables. In addition, your random number generator was wrong.

#include <stdio.h> 
#include <stdlib.h>
#include <time.h>

#define MAX_N 10000
#define MIN_N 2

void Get_Fibonacci()
{
     int fibArray[25];
     int lower = 2, upper = 10000, count = 1, middle = 0,found=0;
     int low=0,high=0;
     int i, FibRange = 50000,n;
     int first = 0, second = 1;

     printf("\n\t Fibonacci sequence:\n");

     fibArray[0]=0;
     fibArray[1]=1;

     printf("%d\n%d\n",fibArray[0],fibArray[1]);

     /* Creates a fibonacci sequence between 0 and 50,000 and store in an array */
     for (i=2; (first+second)<FibRange; i++)
     {
       fibArray[i]=first+second;
       first=second;
       second=fibArray[i];
       printf("%d\n",fibArray[i]);
     }
     high=i-1 /* Using the for loop exit condition, as chux suggested */
     /* Generates a random number between 2 and 10,000 */
     srand(time(0));
     n = rand()%(MAX_N+1-MIN_N)+MIN_N;
     /* Binary search algorithm */
     while (low<=high&&!found)
     {
       middle=(low+high)/2;
       if (n==fibArray[middle])
       {
     count=fibArray[middle];
     found=1; /* To terminate the loop if we have an exact match */
       }
       else if (n<fibArray[middle])
       {
     high=middle-1;
       }
       else
       {
     low=middle+1;
     count=fibArray[middle]; /* Saving the number less than key value */
       }
     }
     printf("\n\tRandom number was: %d\n",n);
     printf("\n\tClosest match was:  %d\n",count);

     return;
 }

int main(void)
{

  Get_Fibonacci();
  return 0;
}

Answer 3

Lambda expression makes these sort of things significantly easier. I suggest learning about lambda and delegates to help with problems like this in the future