// // main.cpp // class12 // // Created by Chad Spensky on 8/2/16. // Copyright © 2016 Chad Spensky. All rights reserved. // #include #include #include #include using namespace std; // Define a variable to decide how much to print const bool VERBOSE = true; // Will return the base raiesed to the exponent // This is done using recusive calls double power(double base, double exponent) { // Are there still multiplications to perform? if (exponent > 0) { return base * power(base,exponent-1); } else { // a 0 exponent is just one return 1; } } // Sort an array using insertion_sort // Ref: https://en.wikipedia.org/wiki/Insertion_sort void insertion_sort(int array_param[], int array_length) { // Go over each position and swap the smallest remaining element into it's place for (int i = 1; i < array_length; i++) { // Starting at the end of the array, keep swapping the element left until the element to the left is no longer smaller int j = i; while (j > 0 && array_param[j] < array_param[j-1]) { swap(array_param[j],array_param[j-1]); // move our j index to the left j--; } } } void bin_search(int array[], int start_idx, int end_idx, int key, bool& found, int& index) { // Does our index start AFTER it ends? if (start_idx > end_idx) { found = false; } else { // Find the midpoint of the search range int mid = (start_idx+end_idx)/2; // Debug output? if (VERBOSE) cout << "bin_search: midpoint at " << mid << "..." << endl; if (array[mid] > key) { // We know that it must be to the left, since the midpoint is > key bin_search(array, start_idx, mid-1, key, found, index); } else if (array[mid] < key) { // We know that it must be to the right, since the midpoint < key bin_search(array, mid+1, end_idx, key, found, index); } else { // We found it! found = true; index = mid; } } } void print_num_array(int array[], int len) { for (int i = 0; i < len; i++) { cout << array[i] << " "; } cout << endl; } int main(int argc, const char * argv[]) { // Let's try our power function vs. the cmath function double base = 2, exponent = 3; cout << "ours: " << base << "^" << exponent << " = " << power(base, exponent) << endl; cout << "cmath: " << base << "^" << exponent << " = " << pow(base,exponent) << endl; // Seed our random number generator srand (time(NULL)); // Let's play with binary search int total_numbers = 25; int numbers[total_numbers]; for (int i = 0; i < total_numbers; i++) { numbers[i] = rand()% total_numbers + 1; } // Print our initial numbers cout << "Unsorted: "; print_num_array(numbers, total_numbers); // Sort our array cout << " Sorted: "; insertion_sort(numbers, total_numbers); // Print the sorted numbers print_num_array(numbers, total_numbers); bool found = false; int found_index = -1; int key = 22; // Let's find our key cout << "Searching for '" << key << "'..." << endl; // Perform a binary search bin_search(numbers, 0, total_numbers, key, found, found_index); // Did we find the number we were searching for? if (found) { cout << "Found number at index " << found_index << "!" << endl; } else { cout << "Could not find the number." << endl; } return 0; }