Binary Search in C++

Binary Search Algorithm

Binary search is an alternative way of searching through a linear set of data. It is much faster than linear search but only works on sorted data, whereas sequential search is for unsorted data. Although sorting takes time, it is (for larger data sets) worth it to sort data and then binary search it than to leave it unsorted and use sequential search. The time complexity of binary search is O(log(n)) because the size of the list is split in half every time it iterates. The way the algorithm works is that it looks at the middle value of a sorted list and checks if it is greater than or less than the value it is searching for. If the middle value is less than the value of what it's searching for, then it splits the list in half and only searches the upper half with the same strategy of splitting. Same goes for if the middle value is greater than the value it's searching for, except with the lower half of the list. Binary search can be either iterative or recursive, but because the recursive version takes up more space O(log(n)), we will implement the iterative version that has a space complexity of O(1).

Below is a C++ implementation of an iterative binary search algorithm:

using namespace std;

#include<iostream>

#include<vector>

int binarySearch(vector<int> input, int value, int lowerIndex, int upperIndex) {

while (lowerIndex < upperIndex) {

//get middle index and and make it an int

int middleIndex = (int)(((lowerIndex + upperIndex) / 2)+1);

//check value at middle index to see if it's greater than or less than the search value

if (input[middleIndex] == value) {

cout << "Found value " << value << "\n";

return value;

}

//cut list in half depending on comparison

if (input[middleIndex] > value) {

upperIndex = middleIndex-1;

}

if (input[middleIndex] < value) {

lowerIndex = middleIndex+1;

}

//if the value is not found

cout << "Couldn't find value " << value << + "\n";

return 0;

}

int main() {

vector<int> sortedList = { 1, 3, 40, 62, 78, 100 };

binarySearch(sortedList, 3, 0, sortedList.size()-1);

binarySearch(sortedList, 62, 0, sortedList.size() - 1);

binarySearch(sortedList, 99, 0, sortedList.size() - 1);

}

Output:

Found value 3

Found value 62

Couldn't find value 99