CC150 9.3

9_3.cpp

/* CC150 9.3 */

#include <iostream>
#include <vector>

using namespace std;

// return one magic index if any
int magicIndex(vector<int> arr, int begin, int end) // arr[begin, end)
{
	if (begin == end) { // no element left in the subarray
		return -1;
	}
	int mid = (begin + end) / 2; // middle of the subarray
	if (arr[mid] == mid)
		return mid;
	else if (arr[mid] < mid)
		return magicIndex(arr, mid + 1, end); // examine the right subaaray
	else
		return magicIndex(arr, begin, mid); // examine the left subaaray
}

int magicIndex(vector<int> arr)
{
	return magicIndex(arr, 0, arr.size());
}

// return all possible magic indices
void magicIndexMult(vector<int> arr, int begin, int end, vector<int> &index)
{
	if (begin == end)
		return;
	int mid = (begin + end) / 2;
	if (arr[mid] >= mid)
		magicIndexMult(arr, begin, mid, index);
	if (arr[mid] == mid)
		index.push_back(mid);
	if (arr[mid] <= mid)
		magicIndexMult(arr, mid + 1, end, index);
}

vector<int> magicIndexMult(vector<int> arr)
{
	vector<int> index;
	magicIndexMult(arr, 0, arr.size(), index);
	return index;
}

// return all possible magic indices, data not dictinct
void magicIndexMultND(vector<int> arr, int begin, int end, vector<int> &index)
{
	if (begin == end)
		return;
	int mid = (begin + end) / 2;
	if (arr[mid] >= mid) // first half
		magicIndexMultND(arr, begin, mid, index);
	else if (arr[mid] >= begin)
		magicIndexMultND(arr, begin, arr[mid] + 1, index);
	if (arr[mid] == mid) // middle
		index.push_back(mid);
	if (arr[mid] <= mid) // second half
		magicIndexMultND(arr, mid + 1, end, index);
	else if (arr[mid] < end)
		magicIndexMultND(arr, arr[mid], end, index);
}

vector<int> magicIndexMultND(vector<int> arr)
{
	vector<int> index;
	magicIndexMultND(arr, 0, arr.size(), index);
	return index;
}

int main()
{
	vector<int> arr;
	int data;
	while (cin >> data)
		arr.push_back(data);
	// one magic index, distinct data
	cout << "Magic index: " << magicIndex(arr) << endl;
	// all magic indices, distinct data
	vector<int> index = magicIndexMult(arr);
	cout << "All magic indices in distinct array: ";
	if (index.empty())
		cout << -1 << endl;
	else {
		for (auto i : index)
			cout << i << " ";
		cout << endl;
	}
	// all magic indices, data not distinct
	index = magicIndexMultND(arr);
	cout << "All magic indices in non-distinct array: ";
	if (index.empty())
		cout << -1 << endl;
	else {
		for (auto i : index)
			cout << i << " ";
		cout << endl;
	}
	return 0;
}

output

-10 -5 2 2 2 3 4 7 9 12 13
^Z
Magic index: 7
All magic indices in distinct array: 7
All magic indices in non-distinct array: 2 7