Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Binary Search, Linear Search, and Bubble Sort implementations from 04/26/2017
#include <vector>
#include <iostream>
int linearSearch(std::vector<int> &vectorToSearch, int itemToTest);
void bubbleSort(std::vector<int> &vectorToSort);
int binarySearch(std::vector<int> &vectorToSearch, int numToTest);
int main() {
std::vector<int> myVector;
myVector.push_back(5);
myVector.push_back(20);
myVector.push_back(18);
myVector.push_back(3);
myVector.push_back(9);
myVector.push_back(4);
myVector.push_back(11);
myVector.push_back(30);
myVector.push_back(2);
myVector.push_back(8);
myVector.push_back(14);
myVector.push_back(22);
myVector.push_back(24);
int idx = linearSearch(myVector, 14); // This should return the index of where the item was found
std::cout << "Found item at index " << idx << std::endl;
std::cout << "Before sorting: " << std::endl;
for (int num : myVector) {
std::cout << num << " ";
}
bubbleSort(myVector);
std::cout << std::endl << "After sorting: " << std::endl;
for (int num : myVector) {
std::cout << num << " ";
}
idx = linearSearch(myVector, 14); // This should return the index of where the item was found
std::cout << "Found item at index " << idx << std::endl;
int x = 1;
std::cin >> x;
idx = binarySearch(myVector, 4); // Should return the index where the item was found
std::cout << "Using binary search, we found 4 at index " << idx << std::endl;
idx = linearSearch(myVector, 4); // This should return the index of where the item was found
std::cout << "Using linear search, we found 4 at index " << idx << std::endl;
idx = binarySearch(myVector, 28); // Should return the index where the item was found
std::cout << "Using binary search, we found 28 at index " << idx << std::endl;
idx = linearSearch(myVector, 28); // This should return the index of where the item was found
std::cout << "Using linear search, we found 28 at index " << idx << std::endl;
//x = 5 / x;
//std::cout << x << std::endl;
//std::cin >> x;
}
void bubbleSort(std::vector<int> &vectorToSort) {
// Save off the size so we don't have to compute it every time.
int size = vectorToSort.size();
// Loop through the list twice to do bubble sort.
// The inner loop swaps items in the vector if needs be.
// The outer loop makes sure we run the swaps enough times to actually be sorted.
for (int i = 0; i < size; i++) {
for (int j = 0; j < size - 1; j++) {
// Do we need to swap?
if (vectorToSort[j] > vectorToSort[j + 1]) {
// Yes, we do.
int temp = vectorToSort[j + 1];
vectorToSort[j + 1] = vectorToSort[j];
vectorToSort[j] = temp;
}
}
}
}
// This should return the index of where the item was found
int linearSearch(std::vector<int> &myVect, int numToTest) {
// loop through the vector
for (int i = 0; i < myVect.size(); i++) {
// if we found the item we were looking for
if (myVect[i] == numToTest) {
// return the index
return i;
}
}
// If we looped through the entire vector and never returned, we never found the item.
// so return -1 as an error condition.
return -1;
}
int binarySearch(std::vector<int> &myVect, int numToTest) {
//if (myVect.size() < 1) {
// return -1;
//}
bool done = false;
int start = 0;
int end = myVect.size();
while (!done) {
// Get midpoint.
int midpoint = floor((start + end / 2));
// Special case ending (base case).
if (end - start <= 2) {
// check the remaining two items
if (myVect[end] == numToTest) return end;
if (myVect[start] == numToTest) return start;
// if numToTest doesn't match either one, we never found the item.
return -1;
}
// Check value at midpoint against numToTest.
if (myVect[midpoint] == numToTest) {
// if midpoint == numToTest return midpoint.
return midpoint;
}
else if (myVect[midpoint] < numToTest) {
// else if midpoint < numToTest
// set start to midpoint
start = midpoint;
}
else {
// else
// set end to midpoint
end = midpoint;
}
}
return -1;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.