# Parallel binary search using Open MPI

### Explanation

Binary search is a search algorithm that can search through sorted data in O(log n) time complexity.

I wanted to implement a parallelised search algorithm utilising binary search, mainly to remind myself of how MPI works.

Below is code that does the following:

• Create a random vector of integers
• Break this vector up into segments and send to these segments to different processes
• Sort and carry out binary search for the target value

### Code

``#include <mpi.h>#include <stdexcept>#include <iostream>#include <vector>#include <algorithm>#include <stdlib.h>/* binary search algorithm that searches for an number in a list */bool binarySearch(int target, const std::vector<int> &list){    int low = 0;    int high = list.size() - 1;    int mid = (low + high) / 2;    while (low <= high)    {        int candidate = list[mid];        if (candidate == target)            return true;        if (target < candidate)            high = mid - 1;        if (target > candidate)            low = mid + 1;        mid = (low + high) / 2;    }    return false;}int main(int argc, char *argv[]){    MPI_Init(&argc, &argv);    int rank;    int number_of_processors;    MPI_Comm_rank(MPI_COMM_WORLD, &rank);    MPI_Comm_size(MPI_COMM_WORLD, &number_of_processors);    /* length of the random number list we will create */    int length = 1000;    int target;    std::vector<int> send_counts;    std::vector<int> displacements;    std::vector<int> list;    /* processor 0 does all the work in creating the list and allocating the number list to all processors */    if (rank == 0)    {        /* Create a random array of numbers, between 0 and 100000 */        for (int i = 0; i < length; i++)            list.push_back(rand() % 100000);        srand(time(NULL));        /* Randomly pick the index for a value we are searching for. Otherwise pick a value that cannot be found */        int selectBit = rand() % 2;        int index;        if (selectBit)        {            index = rand() % (length - 1);            target = list.at(index);        }        else        {            target = 200000;        }        /* number of elements to send to each process */        int load = list.size() / number_of_processors;        int allocated = 0;        /* this loop basically allocates work to each processor */        for (int i = 0; i < number_of_processors; i++)        {            send_counts.push_back(load);            displacements.push_back(allocated);            /* send the load size to other processes so they can create appropriately sized buffer to receive the data */            MPI_Send(&load, 1, MPI_INT, i, 0, MPI_COMM_WORLD);            if (number_of_processors == send_counts.size())                break;            allocated += load;            /* split remaining total load evenly */            load = (list.size() - allocated) / (number_of_processors - send_counts.size());        }    }    int size_of_receive_buffer;    MPI_Recv(&size_of_receive_buffer, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);    std::vector<int> rec_buf(size_of_receive_buffer);    /* scatter the list of random numbers to each processor, based on the load they are calculated to receive */    MPI_Scatterv(&list[0], &send_counts[0], &displacements[0], MPI_INT, &rec_buf[0], size_of_receive_buffer, MPI_INT, 0, MPI_COMM_WORLD);    /* Each array sorts the received data, ready to run binary search */    std::sort(rec_buf.begin(), rec_buf.end());    /* run binary search on the vector of data */    bool result = binarySearch(target, rec_buf);    /* This will be used to aggregate the results */    bool *final_result = nullptr;    /* gather all the search results to process 0 */    MPI_Gather(&result, 1, MPI_CXX_BOOL, &final_result, 1, MPI_CXX_BOOL, 0, MPI_COMM_WORLD);    if (rank == 0)    {        final_result = new bool[number_of_processors];        bool found = false;        /* loop through and check which processors had the matching value */        for (int i = 0; i < number_of_processors; i++)        {            if (final_result[i])            {                std::cout << "processor " << i << " has found the target value of " << target << std::endl;                found = true;            }        }        if (!found)            std::cout << "the target value of " << target << " cannot be found!" << std::endl;        delete[] final_result;    }    /* Do necessary clean up*/    MPI_Finalize();    return 0;}``