This program takes a N sized array of numbers and a target number as input. It then sorts the array and searches for the target number using binary search. If the target number is found, it returns the index of the target number in the sorted array. If the target number is not found, it returns the index where the target number would be inserted to maintain the sorted order.
-
Input:
- Input the size of the array
arraySize
. - Input an array of integers
numbers[]
. - Input the target number
targetNumber
.
- Input the size of the array
-
Sort the Array:
- Time complexity of
std::sort()
: O(nlog n) - Time complexity of
Selection sort algorithm
: O(N*N). - As the sorted algorithm isn't mentioned in the question I implemented the
std::sort()
function from the C++ Standard Library and selection sort algorithm both.
- Time complexity of
-
Binary Search:
- Time complexity: O(log n)
- Implement binary search to find the index of the target number in the sorted array.
- If the target number is found, return its index.
- If the target number is not found, return 0.
-
Handle Insertion Position:
- If the target number is not found, determine the index where it would be inserted based on the sorted order.
- Return this insertion position index.
-
Output:
- Output the index of the target number in the sorted array or the insertion position index.
- Compile the program using a C++ compiler.
- Run the compiled executable.
- Input the size of the array, the array elements, and the target number.
- The program will output the index of the target number in the sorted array or the insertion position index.