I have a C++ algorithm problem:

- an array
**num_list[n]**with n < 200000 - a number
**s**which indicates the number of items in array to pick out. - a requirement that those items have the
*largest intervals*between themselves. - output: the items of the array that should be picked out.

For example: with num_list[6] = { 1, 10, 11, 12, 99, 100 } and s = 3, I would pick 1, 12, 100 because the interval between them are 11, and 88 would be the largest possible.

My approach:

- Step 1: sorted out the array
**num_list[]**in ascending order. - Step 2: make an array
**choice[]**to store possible items in array num_list , assign**choice[0] = num_list[0]** - Step 3: run an outer loop from
**i->s**,

run an inner loop from**j-> size of num_list[]**,

find the next possible item in num_list[] to put into choice[i]

The “sub-problem” that I stumble is step 3: find the next possible item in A to put into X[i].

Intuitively, I would do

- choice[0] = i ; // push the first item
- choice[s-1] = num_list[n-1] // push the last item (can’t do it with vector)
- next
* where*numlist[i] = num_list[j*]* or*A[j*]* is within a “range”. For example:**j**

```
num_list[7] = {1, 9, 10, 11, 12, 90, 100}
s = 4
Step 1: choice[0] = 1, choice[3] = 100;
Step 2: run a looping process and choice[2] = 90, choice[3] = 12
```

I run a kind of “binary search” for step 3 and it doesn’t work yet. On some trials, I would get choice[3] = 9. The code below returns infinitive loop.

Could some one help this poor dummy dude ?

```
#include<iostream>
#include<vector>
#include <algorithm>
#include <cmath>
using namespace std;
int binary_search(int &low, int &high, vector<int> num_list){
cout<<"--binary_search"<<endl;
for (int j = 0; j< 6; j++ ){
if (num_list[j]> low){
cout<<"num_list[j]: "<<num_list[j]<<endl;
return num_list[j];
}
else{
high = low;
int new_low = (high + low)/2;
binary_search(new_low, high, num_list);
}
}
}
// run result for all test cases
void printResult(vector<int>Result){
cout<<"Result: "<<endl;
for (int i : Result){
cout<<i<<" "<<endl;
}
}
// for each T, run a Test Case, accept inputs
void runTestCase(){
// declare inputs as required by problem.
int n, s; //n is the size of num_list
//s is the size of choice
cin >> n >> s;
// vector<int> num_list;
vector<int>num_list;
for (int i = 0; i < n; i++)
{
int num;
cin >> num;
num_list.push_back(num);
}
sort(num_list.rbegin(), num_list.rend(), greater<int>());
// log: test output
cout <<"sorted num_list[i]: "<<endl;
for (int i = 0; i < n; i++)
{
cout << num_list[i] <<" ";
}
cout<<endl;
// solving problem:
vector<int> choice;
// Step 1:
auto iterator = choice.begin();
choice.insert(iterator, num_list[0]); // choice[0]
// choice.insert(iterator + s-1, num_list[n-1]); // choice[s-1] can't really do with vector.
// Step 2:
// for (int i = 0 ; i < s; i++) // since num_list is a vector, do not use for loop
{
int mid = num_list[(n-1)] - num_list[0];
choice.push_back(binary_search(mid, num_list[(n-1)], num_list));
}
printResult(choice);
}
// Solution
void TestCase(int testCase[10], int totalTestCase){
// run test case
for (int i =0; i < totalTestCase; i++ ) {
runTestCase();
}
}
int main(){
int T;
cin>>T;
int testCase [10];
TestCase(testCase, T);
return 0;
}
```