# Difference: BinarySearchCPP ( vs. 1)

#### Revision 12018-05-01 - JimSkon

Line: 1 to 1
>
>
 META TOPICPARENT name="Spring2018"

### Binary Search Example

`<-- SyntaxHighlightingPlugin -->`
```#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
}```
`<-- end SyntaxHighlightingPlugin -->`

 META FILEATTACHMENT attachment="ch14.ppt" attr="" comment="" date="1525192817" name="ch14.ppt" path="ch14.ppt" size="6974976" user="JimSkon" version="1"

Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback