### 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;

}