C++

Forum

 
Binary search or Linear Search for 3d Array

angela325 (4)
I need help with inputting a search array. I tried putting a binary search but I can't get it to work. everything else works up until I put the value I am searching for in the array, then it just crashes.

How it suppose to work:
input 2 coordinates with a value each
then it calculates the distance between them
then it suppose to let user search the coordinates for a value and state if found which coordinate it is at.

Thanks, Angela


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
 
#include "stdafx.h"
#include <iostream>
#include <iomanip>  //for setprecision
#include <math.h>
#include <cstdbool>
#include <cstdlib>	// Needed for rand and srand
#include <ctime>	// Needed for the time function


using namespace std;


//Function Prototypes
void processThroughArray(int[][10][10], int, int, int, int, int, int);
int searchArray(int[][10][10], int, int);
const int SIZE = 1000;

int main()
{

	// establish array and set all values to 0
	int myArray[10][10][10] = { 0 };

	// establish x and y position markers
	int x = 0;
	int y = 0;
	int z = 0;
	int x2 = 0;
	int y2 = 0;
	int z2 = 0;


	// establish input for x and y from the user
	int xInput = 0;
	int yInput = 0;
	int zInput = 0;
	int xInput2 = 0;
	int yInput2 = 0;
	int zInput2 = 0;

	// variable for value entered
	int inputValue = 0;
	int inputValue2 = 0;
	double distance = 0;
	int searchValue;
	int result;


	// Get the user's value and coordinate
	cout << "\nPlease enter the x coordinate ";
	cin >> xInput;
	cout << "\nPlease enter the y coordinate ";
	cin >> yInput;
	cout << "\nPlease enter the z coordinate ";
	cin >> zInput;


	cout << "\nPlease enter the value to place in " << xInput << "," << yInput << "," << zInput << " ";
	cin >> inputValue;

	// Get the user's ending value and coordinate
	cout << "\nPlease enter the ending x coordinate ";
	cin >> xInput2;
	cout << "\nPlease enter the ending y coordinate ";
	cin >> yInput2;
	cout << "\nPlease enter the ending z coordinate ";
	cin >> zInput2;


	cout << "\nPlease enter the value to place in " << xInput2 << "," << yInput2 << "," << zInput2 << " ";
	cin >> inputValue2;

	// place the value in the coordinate
	myArray[xInput][yInput][zInput] = inputValue;
	cout << "\nYou have successfully placed the value " << inputValue << " in coordinate " << xInput << ", " << yInput << ", " << zInput << " ";

	myArray[xInput2][yInput2][zInput2] = inputValue2;
	cout << "\nYou have successfully placed the value " << inputValue2 << " in coordinate " << xInput2 << ", " << yInput2 << ", " << zInput2 << " ";

	//Function performing for loop
	processThroughArray(myArray, x, y, z, x2, y2, z2);

	//calculate distance between the two coordinates
	distance = sqrt(pow(xInput2 - xInput, 2.0) + pow(yInput2 - yInput, 2.0) + pow(zInput2 - zInput, 2.0));
	cout << "\nThe distance between " << xInput << "," << yInput << "," << zInput << " and " << xInput2 << "," << yInput2 << "," << zInput2 << " is ";
	cout << setprecision(4) << distance << endl;


	// indicate end of array processing
	cout << "\nArray Processed" << endl;
	
	//User inputs value to search for
	cout << "Enter the value you wish to look for: ";
	cin >> searchValue;

	result = searchArray(myArray, SIZE, searchValue);

	//If results contains a -1 the value not found
	if (result == -1)
		cout << "That number does not exists in the array.\n";
	else
	{
		cout << "\nValue " << result;
		cout << " in the array.\n";
	}


	system("pause");
	return 0;
}


//**************************************************************************
// Definition of function processThroughArray: Process through the array   *
//the for loop                                                             *
//**************************************************************************
void processThroughArray(int myArray[][10][10], int x, int y, int z, int x2, int y2, int z2)
{

	for (int x = 0, x2 = 0; x<10, x2 < 10; x++, x2++)
	{
		for (int y = 0, y2 = 0; y<10, y2 < 10; y++, y2++)

		{
			for (int z = 0, z2 = 0; z< 10, z2 < 10; z++, z2++)
			{

				// Display the value of the coordinate
				cout << "\nCordinate " << x << ", " << y << ", " << z << " value is " << myArray[x, x2][y, y2][z, z2];

			}
		}
	}



}

//**************************************************************************
// Definition of function searchArray: search array for the value input    *
//				                                                           *
//**************************************************************************
int searchArray(int myArray[][10][10], int size, int value)
{
	int first = 0,
		last = size - 1,
		middle,
		position = -1;
	bool found = false;

	while (!found && first <= last)
	{
		middle = (first + last) / 2;
		if (myArray[middle][middle][middle] = value)
		{
			found = true;
			position = middle;
		}
		else if (myArray[middle][middle][middle] > value)
			last = middle - 1;
		else
			first = middle + 1;
	}
	return position;
}
Duthomhas (13206)
A binary search assumes your sequence is sorted.
If the user is to input stuff, then you cannot assume that.

The simplest method to find it would be a simple linear search.

1
2
3
4
 
for i = 0 to m-1:
  for j = 0 to n-1:
    if (xs[i][j]==value):
      return (i,j)

You'll need to consider how you intend to return an (x,y,z) index into the array (because a single int is not the same as three).

Hope this helps.
angela325 (4)
Here's an update.

I've worked through the linear search but not quite sure what i'm doing wrong at this point.
The issue i'm currently having is that it isn't searching the array correctly.
It finds the first number but can't find the second number.
Also still not able to to put in the coordinates it is found on but i'm sure I need to focus on fixing the first part before moving on to that.

Thanks, Angela

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
 
#include "stdafx.h"
#include <iostream>
#include <iomanip>  //for setprecision
#include <math.h>
#include <cstdbool>
#include <cstdlib>	// Needed for rand and srand
#include <ctime>	// Needed for the time function


using namespace std;


//Function Prototypes
void processThroughArray(int[][10][10], int, int, int, int, int, int);
int searchArray(int[][10][10], int, int, int, int, int, int, int, int);
const int SIZE = 10;

int main()
{

	// establish array and set all values to 0
	int myArray[10][10][10] = { 0 };

	// establish x and y position markers
	int x = 0;
	int y = 0;
	int z = 0;
	int x2 = 0;
	int y2 = 0;
	int z2 = 0;


	// establish input for x and y from the user
	int xInput = 0;
	int yInput = 0;
	int zInput = 0;
	int xInput2 = 0;
	int yInput2 = 0;
	int zInput2 = 0;

	// variable for value entered
	int inputValue = 0;
	int inputValue2 = 0;
	double distance = 0;
	int searchValue;
	int result;


	// Get the user's value and coordinate
	cout << "\nPlease enter the x coordinate ";
	cin >> xInput;
	cout << "\nPlease enter the y coordinate ";
	cin >> yInput;
	cout << "\nPlease enter the z coordinate ";
	cin >> zInput;


	cout << "\nPlease enter the value to place in " << xInput << "," << yInput << "," << zInput << " ";
	cin >> inputValue;

	// Get the user's ending value and coordinate
	cout << "\nPlease enter the ending x coordinate ";
	cin >> xInput2;
	cout << "\nPlease enter the ending y coordinate ";
	cin >> yInput2;
	cout << "\nPlease enter the ending z coordinate ";
	cin >> zInput2;


	cout << "\nPlease enter the value to place in " << xInput2 << "," << yInput2 << "," << zInput2 << " ";
	cin >> inputValue2;

	// place the value in the coordinate
	myArray[xInput][yInput][zInput] = inputValue;
	cout << "\nYou have successfully placed the value " << inputValue << " in coordinate " << xInput << ", " << yInput << ", " << zInput << " ";

	myArray[xInput2][yInput2][zInput2] = inputValue2;
	cout << "\nYou have successfully placed the value " << inputValue2 << " in coordinate " << xInput2 << ", " << yInput2 << ", " << zInput2 << " ";

	//Function performing for loop
	processThroughArray(myArray, x, y, z, x2, y2, z2);

	//calculate distance between the two coordinates
	distance = sqrt(pow(xInput2 - xInput, 2.0) + pow(yInput2 - yInput, 2.0) + pow(zInput2 - zInput, 2.0));
	cout << "\nThe distance between " << xInput << "," << yInput << "," << zInput << " and " << xInput2 << "," << yInput2 << "," << zInput2 << " is ";
	cout << setprecision(4) << distance << endl;


	// indicate end of array processing
	cout << "\nArray Processed" << endl;

	//User inputs value to search for
	cout << "Enter the value you wish to look for: ";
	cin >> searchValue;

	result = searchArray(myArray, SIZE, searchValue, x, y, z, x2, y2,z2);

	//If results contains a -1 the value not found
	
	if (result == -1 )
	{
		cout << "That number does not exists in the array.\n";
	}

	else 
	{
		cout << "\nValue " << searchValue;
		cout << " is located at position: " << result << endl;
		
	}

	


	system("pause");
	return 0;
}


//**************************************************************************
// Definition of function processThroughArray: Process through the array   *
//the for loop                                                             *
//**************************************************************************
void processThroughArray(int myArray[][10][10], int x, int y, int z, int x2, int y2, int z2)
{

	for (int x = 0, x2 = 0; x<10, x2 < 10; x++, x2++)
	{
		for (int y = 0, y2 = 0; y<10, y2 < 10; y++, y2++)

		{
			for (int z = 0, z2 = 0; z< 10, z2 < 10; z++, z2++)
			{

				// Display the value of the coordinate
				cout << "\nCordinate " << x << ", " << y << ", " << z << " value is " << myArray[x, x2][y, y2][z, z2];

			}
		}
	}



}

//**************************************************************************
// Definition of function searchArray: search array for the value input    *
//				                                                           *
//**************************************************************************
int searchArray(int myArray[][10][10], int size, int value,int x, int y, int z, int x2, int y2, int z2)
{
	int index = 0;
	int position = -1;
	bool found = false;

	
	while (index < size && !found)
	{
		if (myArray[index][index][index] == value)
		{
			found = true;
			position = index;
			
		}
		index++;
		
	} 

	return position;
}
Duthomhas (13206)
Your program asks for two inputs only and calculates the distance between (x1, y1, z1) and (x2, y2, z2). (Why?)

I'm not sure what you mean by 'process through [the] array', but it looks like you just want to list all the elements of the array (which is 10*10*10 == 1000 elements!). That's a lot of output for having entered just two non-zero elements.

The search also ignores the advice I gave earlier, compounded by the fact that you are only searching for elements along the diagonal. What if the user puts an element in the array at (1, 2, 3)? That cannot be found by your search.

A search presupposes that you search the entire 3D array, which means you must search every value (z) of every row (y) of every grid (x). You'll need three loops, nested. I gave you an example above (in pseudocode) of searching a 2D array.

Hope this helps.
Topic archived. No new replies allowed.