//*********To DO************ #include  #include  #include  using namespace std; using namespace chrono; // Implement linear search // Return true if x exist in the array A with size n, and return false otherwise bool linear_search(int x, int* A, int n) { //*********To DO************ } // Implement binary search iteratively // Return true if x exist in the array A with size n, and return false otherwise // Hint: don't forget you have while loop :D bool binary_search(int x, int* A, int n) { //*********To DO************ } // Implement binary search // Return true if x exist in the array A with size n, and return false otherwise bool binary_search_recursion(int x, int* A, int s, int n) { //*********To DO************ } // Implement Insertion Sort // You can use a method "swap" to swap the location of two elements // For example swap(A[0],A[n-1]) would swap the first element and last element void insertion_sort(int* A, int n) { //*********To DO************ } int main() { int A[10] = { 1, 3, 4, 7, 9, 11, 14, 15, 17, 20 }; if (!linear_search(0, A, 10)) cout << "0 is not in the array." << endl; else cout << " your linear algorithm is wrong" << endl; if (linear_search(9, A, 10)) cout << "9 is in the array." << endl; else cout << " your linear algorithm is wrong" << endl; if (!binary_search(0, A, 10)) cout << "0 is not in the array." << endl; else cout << " your binary algorithm is wrong" << endl; if (binary_search(17, A, 10)) cout << "17 is in the array." << endl; else cout << " your binary algorithm is wrong" << endl; if (!binary_search_recursion(0, A, 0, 10)) cout << "0 is not in the array." << endl; else cout << " your binary recursion algorithm is wrong" << endl; if (binary_search_recursion(17, A, 0, 10)) cout << "17 is in the array." << endl; else cout << " your binary recursion algorithm is wrong" << endl; int B[11] = { 6, -1, 9, 3, 4, 6, 0, -5, -9, 7, 1 }; insertion_sort(B, 11); cout << "the following array should be sorted" << endl; for (int i = 0; i < 11; ++i) cout << B[i] << " "; cout << endl; return 0; }