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
|
#include <iostream>
#include <cmath>
using namespace std;
const int N = 10;
// A simple print function
void print(int *A)
{
for ( int i = 0; i < N; i++ )
cout << A[i] << " ";
cout << endl;
}
void merge(int* A, int p, int r)
{
int mid = floor((p + r) / 2);
int i1 = 0;
int i2 = p;
int i3 = mid + 1;
// Temp array //////I tried this two different ways but nothing seems to work
//int temp [r-p+1];
int temp = new int[r-p+1];
// Merge in sorted form the 2 arrays
while ( i2 <= mid && i3 <= r )
if ( A[i2] < A[i3] )
temp[i1++] = A[i2++];
else
temp[i1++] = A[i3++];
// Merge the remaining elements in left array
while ( i2 <= mid )
temp[i1++] = A[i2++];
// Merge the remaining elements in right array
while ( i3 <= r )
temp[i1++] = A[i3++];
// Move from temp array to master array
for ( int i = p; i <= r; i++ )
A[i] = temp[i-p];
}
void merge_sort(int* A, int p, int r)
{
if ( p < r )
{
int mid = floor((p + r) / 2);
merge_sort(A, p, mid);
merge_sort(A, mid + 1, r);
merge(A, p, r);
}
}
int sSearch(int A[], int N, int V)
{
for(int i=1;i<=N; i=i+1)
{
if (V==A[i]){
cout<<"Data found at position: "<<i<<endl;
return i;
}
}
}
int bSearch(int A[], int p, int r, int V)
{
if (p<r)
{
int mid =(p+r)/2;
if(V==A[mid])
return mid;
else if (V<A[mid])
return bSearch(A, p, mid-1,V);
else
return bSearch(A, mid+1, r, V);
}
if (V==A[p])
return p;
else return-1;
}
int main(){
int N, i, V, option, p, r;
cout<<"Please enter the size of Array "<<endl;
cin>>N;
int* A ;
A= new int[N];
cout<<"Please enter each numerical value "<<endl;
for(i=1;i<=N;i++)
{
cin>>A[i];
}
merge_sort(A, 0, 9);
cout<<A<<endl;
cout<<"Choose the desired task to perform"<<endl;
cout<<"For Sequence Search select: (option 1)"<<endl;
cout<<"For Binary Search select: (option 2)"<<endl;
cin>>option;
cout<<endl;
if(option ==1)
{
cout<<"Please enter the digit you are searching for "<<endl;
cin>>V;
cout<<endl;
i=sSearch(A, N, V);
if (A[i]!=V){
cout<<"Value Not Found "<<endl;
}
}
else if (option ==2)
{
cout<<"Please enter the digit you are searching for "<<endl;
cin>>V;
cout<<endl;
bSearch(A, p, r, V);
if (A[i]!=V){
cout<<"Value Not Found "<<endl;
}
}
system ("PAUSE");
return 0;
}
|
