I need an improved search algorithm that can be implemented into the given code that isnt as redundant as the brute force algorithm provided. Allows user to set number of elements and max value.

#include  #include  #include  #include  #include  int InsertionSort(int* array, int arraySize){ int numComparisonsSorting = 0; for (int i = 1; i < arraySize; i++){ int value = array[i]; int j = i-1; while (j >= 0){ numComparisonsSorting++; if (array[j] > value) array[j+1] = array[j]; else break; j--; } array[j+1] = value; } return numComparisonsSorting; } 

int main(){ using namespace std; int numElements; cout << "Enter the number of elements: "; cin >> numElements; int maxValue; cout << "Enter the maximum value: "; cin >> maxValue; srand( static_cast(time(nullptr))); int* array = new int[numElements]; int *sortedArray = new int[numElements]; // will be sorted after filled. // filling up the arrays for (int index = 0; index < numElements; index++){ int randValue = 1 + rand() % maxValue; array[index] = randValue; sortedArray[index] = randValue; } int numComparisonsSort = InsertionSort(sortedArray, numElements); for (int targetSum = maxValue; targetSum <= 3*maxValue; targetSum++){ int numComparisonsBruteForce = 0; int numAdditionsBruteForce = 0; for (int i = 0; i < numElements; i++){ for (int j = i+1; j < numElements; j++){ for (int k = j+1; k < numElements; k++){ numComparisonsBruteForce++; numAdditionsBruteForce += 2; if (array[i] + array[j] + array[k] == targetSum){ //cout << i << " " << j << " " << k << " : " << array[i] << " " << array[j] << " " << array[k] << endl; ; } }// k loop }// j loop }// i loop int numComparisonsImprovedSearch = 0; int numAdditionsImprovedSearch = 0; // Implement here your improved search algorithm on the sortedArray // to identify all the 3-element tuples that add up to the particular targetSum cout << targetSum << " " << numComparisonsBruteForce << " " << (numComparisonsSort+numComparisonsImprovedSearch) << " " << numAdditionsBruteForce << " " << numAdditionsImprovedSearch << endl; }// target loop delete[] array; delete[] sortedArray; system("pause"); return 0; }