Hello. I am attending one course which is about

**Data Structures** and

**Algorithms**. Now I am learning about

**Divide and Conqure** algorithms which are more about recursive functions.

But now in the below practice, I get this error:

Error Message:
Test 'SolveTest_Q5OrganizingLottery' exceeded execution timeout period.

Here is the problem description:

**Task**. You are given a set of points on a line and a set of segments on a line. The goal is to compute, for each point, the number of segments that contain this point.
**Input Format**. The first line contains two non-negative integers 𝑠 and 𝑝 defining the number of segments and the number of points on a line, respectively. The next 𝑠 lines contain two integers 𝑎𝑖, 𝑏𝑖 defining the 𝑖-th segment [𝑎𝑖, 𝑏𝑖]. The next line contains 𝑝 integers defining points 𝑥1, 𝑥2, . . . , 𝑥𝑝.
**Constraints**. 1 ≤ 𝑠, 𝑝 ≤ 50000; −108 ≤ 𝑎𝑖 ≤ 𝑏𝑖 ≤ 108 for all 0 ≤ 𝑖 < 𝑠; −108 ≤ 𝑥𝑗 ≤ 108 for all 0 ≤ 𝑗 < 𝑝.
**Output Format**. Output 𝑝 non-negative integers 𝑘0, 𝑘1, . . . , 𝑘𝑝−1 where 𝑘𝑖 is the number of segments which
contain 𝑥𝑖. More formally, 𝑘𝑖 = |{𝑗 : 𝑎𝑗 ≤ 𝑥𝑖 ≤ 𝑏𝑗}| .

For example:

**Sample 1**.
**Input:**
2 3
0 5
7 10
1 6 11
**Output:**
1 0 0
Here, we have two segments and three points. The first point lies only in the first segment while the remaining two points are outside of all the given segments.

**Sample 2**.
**Input:**
1 3
-10 10
-100 100 0
**Output:**
0 0 1

**Sample 3.**
**Input:**
3 2
0 5
-3 2
7 10
1 6
**Output:**
2 0

**What I have tried:**
My function has to get 3 parameters. The first one is for

`starts`

, the second one for

`ends`

, and the third one for

`points`

.

First I sort both the arrays which are for

`starts `

and

`end `

then I define an array which length is equal to the length of

`points`

. Second in a

`for`

loop, I define some conditions. I think the first

`if`

is obvious. but the second and third are used when the element

`point[i]`

does not exist in the

`starts`

or

`ends`

arrays.

Here is my code for

`Binary Search`

:

private static long BinarySearch(long[] a, long l, long h, long key)
{
if (h < l)
{
return -1;
}
long mid = (l + h) / 2;
if (key == a[mid])
{
return mid;
}
else if (key < a[mid])
{
return BinarySearch(a, l, mid - 1, key);
}
else
{
return BinarySearch(a, mid + 1, h, key);
}
}

And this is my main function:

public static long[] OrganizingLottery(long[] starts,long[] ends, long[] points)
{
long s_length = starts.Length;
long e_length = ends.Length;
Array.Sort(starts);
Array.Sort(ends);
long[] res = new long[points.Count()];
long count = 0;
for (long i = 0; i < points.Length; i++)
{
if (points[i] < starts.Min() || points[i] > ends.Max())
{
count = 0;
continue;
}
long index_in_s = BinarySearch(starts, 0, s_length - 1, points[i]);
long index_in_e = BinarySearch(ends, 0, e_length - 1, points[i]);
if (index_in_s == -1)
{
long s_instead = starts.Where(x => x < points[i]).Max();
index_in_s = BinarySearch(starts, 0, s_length - 1, s_instead);
}
if (index_in_e == -1)
{
long e_instead = ends.Where(y => y > points[i]).Min();
index_in_e = BinarySearch(ends, 0, e_length - 1, e_instead);
}
count = index_in_s - index_in_e + 1;
res[i] = count;
}
return res;
}

I know that I have used many LINQ functions 😅, but actually I did not have any other idea for solving this problem.

I will be grateful for any help and advice.

Thanks.

0) Don't use Linq.

1) There is no reason to use recursion in your BinarySearch method.

A binary search is not a good use for recursion. You could also look into tail recursion. It is likely that your instructor said to use recursion as a way for the students to learn when _not_ to use it.

Here is an implementation of a non-recursive generic binary search:

https://www.codeproject.com/Tips/296446/Getting-the-index-of-an-item-in-a-sorted-IList

? Check the data for the Samples: they don't seem to be accurate given the description.

Other possibilities include: a point is outside the line; or, a segment is "not legal" ... however you define "not legal."

If this accurately describes your "context," please help me understand how the sample data shown "work."

in "real world code," skilled programmers often optimize using assumptions about the likely frequency of what types of values the data holds. for example, if i can assume every point is on the line, i can omit testing for that; if the data os organized by magnitude, maybe i don't need to sort.

Different search functions may be used to optimize searching.

If the data is "meaningfully" random, then you may be able to omit sorting. Of course, if sorting is a requirement ...