Binary search: the most fundamental searching algorithm within a sorted array. It finds the position of a target value by comparing the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array. This algorithm logarithmic time LaTeX: O\left(\log n\right) O(log⁡n)comparisons where LaTeX: nn is the number of elements in an array. (Don't worry too much about Big O notation if you don't understand it now) Following is what you are asked to do:
1. Generate 100,000 random integers between 0 - 1,000,000. (Reference: Textbook pp 109 - 113) Then save them to a text file where each line has 5 numbers per line.
2. Next, read the numbers back into a plain old array of integers. (You are not allowed to use vector or any other STL data structures at this point)
3. Use insertion sort (the most efficient LaTeX: O\left(n^2\right)\: O(n2)sorting algorithm to sort the array. You may find more information about insertion sort from wiki. (https://en. wikipedia. org/wiki/Insertion_sort (Links to an external site.))
4. Then your program asks the user to enter a number between 0 - 1,000,000. The program uses the binary search algorithm to determine if the specified number is in the array or not. In the process of determination, your program should display the search step in details as shown below as an example. In any case, the total number of searching should be less than or equal to LaTeX: \log\:100000\:=\:~\:17\: log100000= 17(or 18 if not found)
5. Of course, the test driver should maintain a loop asking if the user wants to play again or not after a search successfully completes. Your test set should include at least the following integer numbers { -100, 0, 123456, 777777, , 1000000, 1000001}
Output example:
please enter a number (0 - 1000000) : 234567
1. 234567 is less than 520349 from randIntArray[50000]
2. 234567 is less than 261002 from randIntArray[25000]
3. 234567 is greater than 126739 from randIntArray[12500]
...
15. 234567 is greater than 234548 from randIntArray [23468]
16. 234567 is less than 234572 from randIntArray[23470]
17. 234567 is less than 234570 from randIndArray[23469]
{ 234567 is not in the list}
Extra credit (7 points):
1) In the insertion sort function, count the total number of comparisons and the total number of swapping against the initial unsorted array
2) Now re-invoke the same insertion sort with the sorted array from the previously sorted array and count the number of comparisons and the number of swapping. While counting the number of comparisons, watch out for integer number overflow error. What should you do if it happens?
3) One more time - Invoke the same insertion sort again with the reversely sorted array from the previously sorted array and count the number of comparisons and the number of swapping. While counting the number of comparisons, watch out for integer number overflow error. What should you do if it happens?
4) Describe your observation in a few sentences by comparing their performance results in 1) , 2) and 3).