-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDotnetArray.cs
134 lines (125 loc) · 4.19 KB
/
DotnetArray.cs
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
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStruct
{
public class DotnetArray<T>
{
private T[] instanceArray;
private int nElemens;
public List<int> visitedIndexOnBinarySearch = new List<int>();
public IEnumerable visitedIndexOnLinearSearch = new List<int>();
public bool found;
// le constructeur de l Array
public DotnetArray(int maxElement)
{
instanceArray = new T[maxElement];
nElemens = 0;
}
// Naive version
public bool Find(T searchKey)
{
int j;
for (j = 0; j < nElemens; j++)
{
if (instanceArray[j].Equals(searchKey))
{
return true;
}
}
return false;
}
// Binary search
// oriented to be exposed at an API call
// O(logN), each comparison is function 2**n, so to find the average step, we log so logN
public SearchResult BinarySearch(long[] currentArray, long searchKey)
{
int lowerBound = 0;
int upperBound = currentArray.Length - 1;
int currentIndex;
int k = 0;
Array.Sort(instanceArray);
while (true)
{
currentIndex = (lowerBound + upperBound)/ 2;
visitedIndexOnBinarySearch.Add(currentIndex);
if (currentArray[currentIndex] == searchKey)
{
this.found = true;
return new SearchResult() { Found = this.found, VisitedIndex = visitedIndexOnBinarySearch };
} else if (lowerBound > upperBound)
{
this.found = false;
return new SearchResult() { Found = this.found, VisitedIndex = visitedIndexOnBinarySearch };
}
else
{
if (currentArray[currentIndex] < searchKey)
{
lowerBound = currentIndex + 1;
} else
{
upperBound = currentIndex - 1;
}
}
k += 1;
}
}
// Linear search
// oriented to be exposed at an API call
// O(N), if the list is ordered and searchKey is the last item:
public SearchResult LinearSearch(long[] currentArray, long searchKey)
{
for (int currentIndex = 0; currentIndex < currentArray.Length; currentIndex++)
{
if (currentArray[currentIndex] == searchKey)
{
return new SearchResult() { Found = this.found, VisitedIndex = (List<int>)Enumerable.Range(0, currentIndex) };
}
}
return new SearchResult() { Found = false, VisitedIndex = (List<int>)Enumerable.Range(0,currentArray.Length) };
}
public void Insert(T value)
{
instanceArray[nElemens] = value;
nElemens += 1;
}
public bool Delete(T value)
{
int j;
for (j = 0; j < nElemens; j++)
{
if (instanceArray[j].Equals(value))
{
// rempli l espace memoire vide
// decalage a gauche
// value at k th will be erased
for (int k = j; k < nElemens; k++)
{
instanceArray[k] = instanceArray[k + 1];
}
// decremente le nbre total d element car on a perdu 1:
nElemens -= 1;
return true;
}
}
return false;
}
public T[] toArray()
{
return instanceArray as T[];
}
}
public class SearchResult
{
public List<int> VisitedIndex {get;set;}
public bool Found { get; set; }
}
public class BinarySearchQuery
{
public long[] Array { get; set; }
public long SearchKey { get; set; }
}
}