Binary Search ALDS Lab

BinarySearch.cpp

#include <iostream>
#include <vector>
#include <algorithm>

#define tmpl8 template <typename T>

using namespace std;

int binCount = 0;

/* Function Declarations */
bool choice();
tmpl8 void exec(vector<T> &v);
tmpl8 void print(vector<T> v);
tmpl8 void input(vector<T> &v, int num);
tmpl8 int part(vector<T> &v, int low, int high);
tmpl8 void quicksort(vector<T> &v, int low, int high);
tmpl8 void indices(vector<T> v, int index);
tmpl8 int binarySearch(vector<T> &v, T element);


/* Main Program */
int main() {
    bool running = true;
    while (running) {
        cout << "Enter the type of data you want to enter : \n\t1. Integer\n\t2. "
             "Character\n\t3. String\n\t4. Floating Point"
             << endl;
        int type;
        cin >> type;

        switch (type) {
            case 1: {
                vector<int> v;
                exec(v);
                break;
            }
            case 2: {
                vector<char> v;
                exec(v);
                break;
            }
            case 3: {
                vector<string> v;
                exec(v);
                break;
            }
            case 4: {
                vector<float> v;
                exec(v);
                break;
            }
            default: {
                cout << "Invalid selection\nProgram will terminate..." << endl;
                return 1;
            }
        }
        cout << "Do you want to run the program again? (Y/N) ";

        if (!choice()) running = false;
    }

    cout << "Program Ended" << endl;
    return 0;
}


/* Execution Program */
tmpl8 void exec(vector<T> &v) {
    bool loop = true;

    cout << endl << "Enter the number of elements : ";
    int num;
    cin >> num;
    input(v, num);
    quicksort(v, 0, v.size() - 1);
    cout << endl << "Sorted Data :" << endl;
    print(v);

    while (loop) {
        cout << endl << "Enter the element to find : ";
        T data;
        cin >> data;
        // Reset counter to zero
        binCount = 0;
        int loc = binarySearch(v, data);
        if (loc == -1) {
            cout << endl << "Item not found" << endl;
        } else {
            cout << endl << "Item was found in the following location(s) :" << endl << data << " => ";
            indices(v, loc);
        }
        cout << "Binary Search Algorithm ran " << binCount << " times." << endl
             << endl;
        cout << "Do you want to find another element? (Y/N) ";

        if (!choice()) loop = false;
    }
}

bool choice() {
    char c;
    cin >> c;
    if (c == 'Y' || c == 'y') return true;
    return false;
}

tmpl8 void print(vector<T> v) {
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}

tmpl8 void input(vector<T> &v, int num) {
    for (int i = 0; i < num; i++) {
        T data;
        cin >> data;
        v.push_back(data);
    }
}

/* Binary Search Algorithm */
tmpl8 int binarySearch(vector<T> &v, T element) {
    int beg = 0, end = v.size() - 1, mid = v.size() / 2;

    while (beg <= end) {
        binCount++;
        if (element > v[mid]) {
            beg = mid + 1;
        } else if (element < v[mid]) {
            end = mid - 1;
        } else {
            return mid;
        }
        mid = beg + (end - beg) / 2;
    }

    return -1;
}

/* Duplicate Finder */
tmpl8 void indices(vector<T> v, int index) {
    T data = v[index];
    cout << index;
    int i = index;

    while (i > 0 && v[--i] == data) {
        cout << " " << i;
    }

    i = index;
    while (i < v.size()-1 && v[++i] == data) {
        cout << " " << i;
    }

    cout << endl << endl;
}

/* Quick Sort */
tmpl8 int part(vector<T> &v, int low, int high) {
    T pivot = v[high];
    for (int j = low; j < high; j++) {
        if (v[j] <= pivot) {
            swap(v[low], v[j]);
            low++;
        }
    }
    swap(v[low], v[high]);
    return low;
}

tmpl8 void quicksort(vector<T> &v, int low, int high) {
    if (low < high) {
        int p = part(v, low, high);
        quicksort(v, low, p - 1);
        quicksort(v, p + 1, high);
    }
}