Tags:
create new tag
view all tags

Binary Search Example

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> inputData();
void outputData(vector<int> data);

int rBinarySearch(vector<int> sortedArray, int first, int last, int key);

int main() {

    vector<int> data = inputData();
    sort(data.begin(), data.end());
    outputData(data);

    int value;

    do {
        cout << "Enter number to search for (-1 if done):";
        cin >> value;
        int loc = rBinarySearch(data, 0, data.size() - 1, value);
        if (loc >= 0) {
            cout << "The value " << value << " found at index " << loc << endl;
        } else {
            cout << "The value " << value << " not found, should be at " << -loc << endl;
        }
    } while (value > 0);

    return 0;
}

vector<int> inputData() {
    cout << "Enter some non-negative integers, -1 when done.\n";
    vector<int> values;
    int v;
    do {
        cin >> v;
        if (v >= 0) {
            values.push_back(v);
        }
    } while (v >= 0);
    return values;
}

void outputData(vector<int> data) {
    for (int i = 0; i < data.size(); i++) {
        cout << data[i] << " ";
    }
    cout << endl;
}

int rBinarySearch(vector<int> sortedArray, int first, int last, int key) {
    // function:
    //   Searches sortedArray[first]..sortedArray[last] for key.  
    // returns: index of the matching element if it finds key, 
    //         otherwise  -(index where it could be inserted)-1.
    // parameters:
    //   sortedArray in  array of sorted (ascending) values.
    //   first, last in  lower and upper subscript bounds
    //   key         in  value to search for.
    // returns:
    //   index of key, or -insertion_position -1 
    //                 if key is not in the array.

    if (first <= last) {
        int mid = (first + last) / 2; // compute mid point.
        if (key == sortedArray[mid])
            return mid; // found it.
        else if (key < sortedArray[mid])
            // Call ourself for the lower part of the array
            return rBinarySearch(sortedArray, first, mid - 1, key);
        else
            // Call ourself for the upper part of the array
            return rBinarySearch(sortedArray, mid + 1, last, key);
    }
    return -(first + 1); // failed to find key
}
Topic attachments
I Attachment History Action Size Date Who Comment
PowerPointppt ch14.ppt r1 manage 6811.5 K 2018-05-01 - 16:40 JimSkon  
Topic revision: r1 - 2018-05-01 - JimSkon
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback