I am trying to solve a tricky problem involving a sorted array. Say I have an array of sorted integers (8, 6, 4, 1) and given the value x I need to check the array to see if any two numbers add up to x. This needs to be done in linear time. So far I have come up with this:

#include <iostream>

using namespace std;

bool sum(int arr[], int n, int k)
{
	int temp1(0), temp2(0);

	while (arr[temp1] + arr[temp1 + 1] <= k);
	{
		if (arr[temp1] + arr[temp1 + 1] == k)
		{
			return true;
		}
		
		if (arr[temp1] + arr[temp1 + 1] < k)
		{
			temp1 += 1;
		}
	}

	temp2 = temp1 + 1;

	for (temp1; temp1 > 0; --temp1)
	{
		if (arr[temp1] + arr[temp1] == k)
		{
			return true;
		}
	}

	return false;
}

int main()
{
	int list[4] = {8, 6, 4, 1};

	bool result = true;
	result = sum2(list, 4, 10);

	cout << result << endl;

	return 0;
}

It does not work and I am entirely at loss as to how I may go about getting this problem to work. I know how to do it in quadratic time using two loops, but doing it in linear time is getting to be frustratingly difficult.

Went back to the drawing board and wrote an entirely new algorithm and solved it.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.