In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of March 31st
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #04 exercise sheet]

In this problem you should submit a file containing the function as described (without any main function). Inside the function do not print anything that was not asked!

[PII031] The Perfect Ice Cream

At Scoops Ahoy, Steve and Robin are on a mission to find the perfect ice cream flavor. The flavors are neatly arranged in alphabetical order, and each flavor is assigned a unique number. Steve, being Steve, suggests checking each flavor one by one until they find the one they want.

But Robin, the genius that she is, knows the flavors are sorted and insists that there’s a faster way to find the right one.

Your task is to help Robin efficiently find the first occurrence of a given flavor’s number in the sorted menu.

The Problem

Write a function int search(int x, int a[], int n) that receives an integer x, and an array a[] of size n that is sorted in strictly increasing order. If x exists on the array, it should return its index (0-based). If it’s not on the array, return -1.

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

Additionally, it is guaranteed the array will be sorted in strictly increasing order, with no repeated values.

Submission

You should submit a .c file containing the requested function, without any main function and without printing anything. You can however create additional methods, if you need them.

Mooshak will use the following code to link to your function, read the inputs and call your method, printing its result.

#include <stdio.h>

// Forward declaration of function to implement
int search(int, int [], int);

int main(void) {

  // Read array of n integers
  int n;
  scanf("%d", &n);
  int a[n];
  for (int i=0; i<n; i++)
    scanf("%d", &a[i]);

  // Print the array (assume size >= 1)
  printf("a = [%d", a[0]);
  for (int i=1; i<n; i++)
    printf(",%d", a[i]);
  printf("]\n");
  
  // Read the number of queries to make
  int q;
  scanf("%d", &q);
  for (int i=0; i<q; i++) {
    // for each query, read x and print the result of searching for x
    int x;
    scanf("%d", &x);
    printf("search(%d, a, %d) = %d\n", x, n, search(x, a, n));
  }

  return 0;
}

NOTE: the limits are really high and you must have an efficient solution that can compute this quickly.
A solution that simply tries to traverse the entire array and check if the number is there will most likely have Time Limit Exceeded.
Your program will need to be able to answer 100 000 queries in an array with 100 000 integers in less than one second.

6
2 3 4 6 8 42
8
50 42 1 2 3 4 5 8

a = [2,3,4,6,8,42]
search(50, a, 6) = -1
search(42, a, 6) = 5
search(1, a, 6) = -1
search(2, a, 6) = 0
search(3, a, 6) = 1
search(4, a, 6) = 2
search(5, a, 6) = -1
search(8, a, 6) = 4